查找二叉树（Java）的两个树叶之间的最大路径总和

Question

我正在努力解决以下问题：“给定一个二叉树，其中每个节点元素都包含一个数字。到另一个。 最大总和路径可能会或可能不会经过根。“我想写这里讨论的O（n）解决方案：http://www.geeksforgeeks.org/find-maximum-path-sum-two-leaves-binary-tree/但我有一个问题，因为Java是通过值传递的。有人可以帮忙吗？

编辑：这是我的方法

private static int fromRoot(TreeNode root, int[] res){ 
    if(root == null) 
     return 0; 
    int left = fromRoot(root.left, res) + root.val; 
    int right = fromRoot(root.right, res) + root.val; 
    int max = Math.max(Math.max(left, right), left+right+root.val); 
    if(max > res[0]) 
     res[0] = max; 
    return Math.max(left, right); 
} 

的int变量res我保存输出。这段代码的作用是给出树中所有节点的总和。

Answer 1

您的代码与文章中的代码明显不同（与使用的语言无关）。

在你的代码，它是：

int left = fromRoot(root.left, res) + root.val; 
int right = fromRoot(root.right, res) + root.val; 
... 
return Math.max(left, right); 

但它应该是：

int left = fromRoot(root.left, res); 
int right = fromRoot(root.right, res); 
... 
return Math.max(left, right) + root.val;