Given a binary tree in which each node contains an integer number. Find the maximum possible subpath sum(both the starting and ending node of the subpath should be on the same path from root to one of the leaf nodes, and the subpath is allowed to contain only one node). (not necessary to ending at the leaf node)
Assumptions
- The root of given binary tree is not null1
Examples
-5
/ \
2 11
/ \
6 14
/
-3
The maximum path sum is 11 + 14 = 25
How is the binary tree represented?
We use the level order traversal sequence with a special symbol "#" denoting the null node.
For Example:
The sequence [1, 2, 3, #, #, 4] represents the following binary tree:
1
/ \
2 3
/
4
solution1 : bottom up ( 3 steps of tree recursion algorithm)
/**
* public class TreeNode {
* public int key;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int key) {
* this.key = key;
* }
* }
*/
public class Solution {
public int maxPathSum(TreeNode root) {
public class Solution {
public int maxPathSum(TreeNode root) {
// Write your solution here.
if (root == null) {
return 0;
}
int[] globalMax = {Integer.MIN_VALUE};
helper(root, globalMax);//return the curmax
return globalMax[0];
}
// bottom up solution
// at current level: curmax = max(max(left,right),0) + root.key
// return curmax to upper level
private int helper(TreeNode root, int[] globalMax) {
// base case
if (root == null) {
return 0;
}
int left = Math.max(helper(root.left, globalMax), 0);
int right = Math.max(helper(root.right, globalMax), 0);
//pitfall: curmax need to include root.key, otherwise it could happen
// none of node included in the path
int curMax = Math.max(left,right) + root.key;
globalMax[0] = Math.max(globalMax[0],curMax);
return curMax;
}
}
solution2: top to bottom
/**
* public class TreeNode {
* public int key;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int key) {
* this.key = key;
* }
* }
*/
public class Solution {
public int maxPathSum(TreeNode root) {
// Write your solution here.
if (root == null) {
return 0;
}
int[] globalMax = {Integer.MIN_VALUE};
helper(root, globalMax,Integer.MIN_VALUE\);
return globalMax[0];
}
private void helper(TreeNode root, int[] globalMax,int curMax) {
// base case
if (root == null) {
return;
}
//key point curMax < 0, no need to carry down to the next level
curMax = Math.max\(curMax,0\) + root.key;
globalMax\[0\] = Math.max\(globalMax\[0\],curMax\);
helper\(root.left,globalMax,curMax\);
helper\(root.right,globalMax,curMax\);
}
}
1. 直上直下（any node to any node) ↩