Найти максимальную сумму пути между двумя листами двоичного дерева (Java)

Question

Я борюсь со следующим вопросом: «Учитывая двоичное дерево, в котором каждый элемент узла содержит число. Найдите максимально возможную сумму из одного листового узла к другому. Путь максимальной суммы может или не может проходить через корень ». Я хочу написать решение O (n), обсуждаемое здесь: http://www.geeksforgeeks.org/find-maximum-path-sum-two-leaves-binary-tree/, но у меня проблема, так как java передается по значению. Может кто-нибудь помочь?

EDIT: это мой метод

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;