Problem
Given a binary tree, find the path with largest node sums, the path can start at any node and end at any node.For example:
Given:
3
/ \
5 4
the output should be 12.
Solution
Let's analyze the simplest condition. the total is the max(root.left + root.value, root.right + root.value, root.left + root.right + root.value). This node could contribute to paths in the parent nodes. The contribution is max(root.value + root.left, root.value + root.right, root.value). We can do a post order traversal, with exit condition root == null.
class MaxSum {
private int max = Integer.MIN_VALUE;
public int sum(Node root) { //3
if(root == null) return 0;
int lsum = sum(root.left); //5
int rsum = sum(root.right); //-4
max = Math.max(max, max(lsum + root.value, rsum + root.value, lsum + rsum + root.value));
return max(root.value + lsum, root.value + rsum, root.value);
}
private int max(int a, int b, int c) {
int t = Math.max(a, b);
return Math.max(t, c);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
public static void main(String...args) {
MaxSum ms = new MaxSum();
Node root = new Node(3, new Node(5, null, null), new Node(4, new Node(-3, null, null), new Node(-2, null, null)));
ms.sum(root);
System.out.println(ms.max);
}
}
private int max = Integer.MIN_VALUE;
public int sum(Node root) { //3
if(root == null) return 0;
int lsum = sum(root.left); //5
int rsum = sum(root.right); //-4
max = Math.max(max, max(lsum + root.value, rsum + root.value, lsum + rsum + root.value));
return max(root.value + lsum, root.value + rsum, root.value);
}
private int max(int a, int b, int c) {
int t = Math.max(a, b);
return Math.max(t, c);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
public static void main(String...args) {
MaxSum ms = new MaxSum();
Node root = new Node(3, new Node(5, null, null), new Node(4, new Node(-3, null, null), new Node(-2, null, null)));
ms.sum(root);
System.out.println(ms.max);
}
}
We need to exam each node, the time cost is O(N). The recursive call stack of sum has logN layers, each function call has few variables, so the extra space is O(logN) on average and O(N) at worst.
