Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
Analysis
- A path from start to end, goes up on the tree for 0 or more steps, then goes down for 0 or more steps. Once it goes down, it can't go up. Each path has a highest node, which is also the lowest common ancestor of all other nodes on the path.
- A recursive method maxPathDown(TreeNode node) (1) computes the maximum path sum with highest node is the input node, update maximum if necessary (2) returns the maximum sum of the path that can be extended to input node's parent.
Example 1:
-10
/ \
2 -3
/ \ / \
3 4 5 7
Code
public class Solution {
int maxValue = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPathDown(root);
return maxValue;
}
//以node为最高点的path sum最大值，注意这个函数返回的是左右子树只能取其中一条，因为当返回用来算通过parent节点的path sum时，下面level的节点不可以同时取左右子树
//update maxValue when necessary (maxValue: 左右子树可以同时包含)
private int maxPathDown(TreeNode node){
if (node == null) return 0;
//left: 包含左child的path最大值，如果最大值为负数，取0（不取）
int left = Math.max(0, maxPathDown(node.left));
//right: 包含右child的path最大值，如果最大值为负数，取0（不取）
int right = Math.max(0, maxPathDown(node.right));
//算包含该node的path最大值，更新maxValue if necessary
maxValue = Math.max(maxValue, left+right+node.val);
//返回包含该node的path最大值
return Math.max(left, right) + node.val;
}
}