/*
find the maximum sum of path
a path can have any node as start or end nodes
for example the following tree has path sum 35
10
/ \
5 20
*/
public class GlobalOptimumTwo {
public static int maxSum = Integer.MIN_VALUE;
public static void main(String...arg) {
int[] values = {10, -5, -20, 3, -15, 7, 26, -9, 14};
System.out.println("Layer order");
BTree root = buildTree(values);
BTreePrinter.printNode(root);
maxPathSum(root);
System.out.println("the maximum sum of path is:");
System.out.println(maxSum);
}
public static int maxPathSum(BTree root) {
if(root == null) {
return 0;
}
int leftSum = 0, rightSum = 0, total = 0;
leftSum = maxPathSum(root.left);
rightSum = maxPathSum(root.right);
if(leftSum > 0)
total += leftSum;
if(rightSum > 0)
total += rightSum;
total += root.value;
maxSum = Math.max(total, maxSum);
return total;
}
//build a binary search tree
public static BTree buildTree(int[] values) {
BTree root = null;
for(int value : values) {
root = insert(root, value);
}
return root;
}
public static BTree insert(BTree root, int value) {
if(root == null) {
return new BTree(value, null, null);
}
if(value > root.value) {
root.right = insert(root.right, value);
return root;
}
if(value < root.value) {
root.left = insert(root.left, value);
return root;
}
root.value = value;
return root;
}
}
