Given a non-empty 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 must contain at least one node and does not need to go through the root.
Example 1:
Input: [1,2,3] 1 / \ 2 3 Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 Output: 42
PostOrder traverse the whole tree. For each node calculate Max(root, root+leftSide, root+rightSide, leftSide+root+rightSide ), update max[0] (which is used to store max value), then return Max (root+leftSide, root+rightSide, root)
https://leetcode.com/problems/binary-tree-maximum-path-sum/discuss/39775/Accepted-short-solution-in-Java
- 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.
maxValue = Math.max(maxValue, left + right + node.val);
return Math.max(left, right) + node.val;
maxValue is the value which recording whether this current root is the final root, so we use
left + right + node.val. But to the upper layer(after return statement), we cannot choose both left and right brunches, so we need to select the larger one, so we usemax(left, right) + node.val to prune the lower brunch.public class Solution {
int maxValue;
public int maxPathSum(TreeNode root) {
maxValue = Integer.MIN_VALUE;
maxPathDown(root);
return maxValue;
}
private int maxPathDown(TreeNode node) {
if (node == null) return 0;
int left = Math.max(0, maxPathDown(node.left));
int right = Math.max(0, maxPathDown(node.right));
maxValue = Math.max(maxValue, left + right + node.val);
return Math.max(left, right) + node.val;
}
}public int maxPathSum(TreeNode root) {
int[] max = new int[1];
max[0] = Integer.MIN_VALUE;
maxPathSum(max, root);
return max[0];
}
private int maxPathSum(int[] max, TreeNode root){
if(root == null)
return 0;
int leftMax = Math.max(0, maxPathSum(max, root.left));
int rightMax = Math.max(0, maxPathSum(max, root.right));
max[0] = Math.max(max[0], root.val+leftMax+rightMax);
return root.val+Math.max(leftMax,rightMax);
} int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
helper(root);
return max;
}
// helper returns the max branch
// plus current node's value
int helper(TreeNode root) {
if (root == null) return 0;
int left = Math.max(helper(root.left), 0);
int right = Math.max(helper(root.right), 0);
max = Math.max(max, root.val + left + right);
return root.val + Math.max(left, right);
}
For each node like following, there should be four ways existing for max path:
1. Node only （因为本题中的节点可能是负值！）2. L-sub + Node
3. R-sub + Node
4. L-sub + Node + R-sub
Keep trace the four path and pick up the max one in the end.
public static int maxPathSum(TreeNode root) {
int[] max = {Integer.MIN_VALUE}; // 因为Java里都是pass by value所以利用数组传！
rec(root, max);
return max[0];
}
public static int rec(TreeNode root, int[] max){
if(root == null){
return 0;
}
int leftSubtreeMaxSum = rec(root.left, max); // 左子树的最大和
int rightSubtreeMaxSum = rec(root.right, max); // 右子树的最大和
int arch = leftSubtreeMaxSum + root.val + rightSubtreeMaxSum; // 从左子树经过root到右子树的最大和
// 表示通过root节点能走到root的parent的最大和，这个值作为返回对象返给调用父函数
// 只有3中情况: 1 从左子树到root再到parent
// 2 从右子树到root再到parent
// 3 直接从root到parent
// 注意arch那条路是不可能走到parent，因为那条路已经经过root了，除非折回来重复走！但这是不允许的
int maxPathAcrossRootToParent = Math.max(root.val, Math.max(leftSubtreeMaxSum, rightSubtreeMaxSum)+root.val);
// max[0] 保存在所有递归过程中的最大值，这时也要考虑arch可能最大
max[0] = Math.max(max[0], Math.max(arch, maxPathAcrossRootToParent));
return maxPathAcrossRootToParent;
}
http://www.jiuzhang.com/solutions/binary-tree-maximum-path-sum/http://ying.ninja/?p=964
private class ResultType {
int singlePath, maxPath;
ResultType(int singlePath, int maxPath) {
this.singlePath = singlePath;
this.maxPath = maxPath;
}
}
private ResultType helper(TreeNode root) {
if (root == null) {
return new ResultType(Integer.MIN_VALUE, Integer.MIN_VALUE);
}
// Divide
ResultType left = helper(root.left);
ResultType right = helper(root.right);
// Conquer
int singlePath =
Math.max(0, Math.max(left.singlePath, right.singlePath)) + root.val;
int maxPath = Math.max(left.maxPath, right.maxPath);
maxPath = Math.max(maxPath,
Math.max(left.singlePath, 0) +
Math.max(right.singlePath, 0) + root.val);
return new ResultType(singlePath, maxPath);
}
https://leetcode.com/discuss/43797/elegant-java-solution
the key point is replacing the negative max value and null nodes value with 0, thus there would no negative value in any binary tree, and we need not care about any single node.
public class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
helper(root);
return max;
}
// helper returns the max branch
// plus current node's value
int helper(TreeNode root) {
if (root == null) return 0;
int left = Math.max(helper(root.left), 0);
int right = Math.max(helper(root.right), 0);
max = Math.max(max, root.val + left + right);
return root.val + Math.max(left, right);
}
}http://www.chenguanghe.com/binary-tree-maximum-path-sum/
遍历所有node, 如果当前的path sum小于0, 那么是对sum没帮助的, 只关心大于0的. 然后找到最大就行了
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if(root == null)
return 0;
helper(root);
return max;
}
public int helper(TreeNode root) {
if (root == null) return 0;
int left = Math.max(helper(root.left), 0);
int right = Math.max(helper(root.right), 0);
max = Math.max(max, root.val + left + right);
return root.val + Math.max(left, right);
}
[leetcode] Binary Tree Maximum Path Sum |树中任意两点间最大path sum
arch代表穿过当前节点的路径（左边一支儿+自己节点+右边一支儿）。
注意树的节点可以是负数，所以arch不一定是最长的。
每次return以root（当前节点）开头最大的单只path sum。
后来发现，没有分清最大值和递归函数的返回值。在求值函数里面不能把计算出来的最大值作为返回值返回回去，否则会有问题。
全局最优解 和局部最优解
public int maxPathSum(TreeNode root) {
int[] res = new int[1];
res[0] = Integer.MIN_VALUE;
maxPath(root, res);
return res[0];
}
private int maxPath(TreeNode root, int[] res) {
if (root == null)
return 0;
int left = maxPath(root.left, res);//左边一支儿（不算自己）
int right = maxPath(root.right, res);
int arch = left + right + root.val; //穿过自己
int single = Math.max(root.val, Math.max(left, right) + root.val);（算上自己）
res[0] = Math.max(res[0], Math.max(arch, single));//update结果
return single;
}
http://hehejun.blogspot.com/2015/01/leetcodebinary-tree-maximum-path-sum.htmlUse instance field.
注意path可以在tree里的任意节点开始和结束，我们需要用bottom-up的方法，在每一个节点，先递归找到左子树和右子树的一直朝上走的maximum path sum，然后两边与自己的值的和若比现在的max sum大，更新sum。然后从左子树和右子树的最大值挑一个大的与自己的和return上去，注意如果小于等于0的话就直接return0，因为会使得值变得更小。
public class Solution {
private int sum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
findMaxSum(root);
return sum;
}
private int findMaxSum(TreeNode node) {
if (node == null)
return 0;
int left = findMaxSum(node.left);
int right = findMaxSum(node.right);
int currSum = left + node.val + right;
if (currSum > sum)
sum = currSum;
int retPath = left >= right? left + node.val: right + node.val;
return retPath > 0? retPath: 0;
}
}
http://www.programcreek.com/2013/02/leetcode-binary-tree-maximum-path-sum-java/
1) Recursively solve this problem
2) Get largest left sum and right sum
2) Compare to the stored maximum
public int maxPathSum(TreeNode root) { int max[] = new int[1]; max[0] = Integer.MIN_VALUE; calculateSum(root, max); return max[0]; } public int calculateSum(TreeNode root, int[] max) { //use int[] if (root == null) return 0; int left = calculateSum(root.left, max); int right = calculateSum(root.right, max); int current = Math.max(root.val, Math.max(root.val + left, root.val + right)); max[0] = Math.max(max[0], Math.max(current, left + root.val + right)); return current; } |
- int fun(TreeNode *root, int &max) //递归计算单向路径最大和
- {
- if(root == NULL)
- return 0;
- int left = fun(root->left, max);
- if(left < 0) //如果为负就剪掉
- left = 0;
- int right = fun(root->right, max);
- if(right < 0) //如果为负就剪掉
- right = 0;
- // 在递归过程中考察以root为中心的双向路径的和
- if(left + right + root->val > max)
- max = left + right + root->val;
- if(left > right)
- return left + root->val;
- else
- return right + root->val;
- }
// An object of Res is passed around so that the// same value can be used by multiple recursive calls.class Res { public int val;}class BinaryTree { // Root of the Binary Tree Node root; // This function returns overall maximum path sum in 'res' // And returns max path sum going through root. int findMaxUtil(Node node, Res res) { // Base Case if (node == null) return 0; // l and r store maximum path sum going through left and // right child of root respectively int l = findMaxUtil(node.left, res); int r = findMaxUtil(node.right, res); // Max path for parent call of root. This path must // include at-most one child of root int max_single = Math.max(Math.max(l, r) + node.data, node.data); // Max Top represents the sum when the Node under // consideration is the root of the maxsum path and no // ancestors of root are there in max sum path int max_top = Math.max(max_single, l + r + node.data); // Store the Maximum Result. res.val = Math.max(res.val, max_top); return max_single; } int findMaxSum() { return findMaxSum(root); } // Returns maximum path sum in tree with given root int findMaxSum(Node node) { // Initialize result // int res2 = Integer.MIN_VALUE; Res res = new Res(); res.val = Integer.MIN_VALUE; // Compute and return result findMaxUtil(node, res); return res.val; }https://gist.github.com/benjaminwu7/4700454#file-leetcode-binary-tree-maximum-path-sum-java
[LintCode] 475 Binary Tree Maximum Path Sum II
https://xuezhashuati.blogspot.com/2017/04/lintcode-475-binary-tree-maximum-path.html
Given a binary tree, find the maximum path sum from root.
The path may end at any node in the tree and contain at least one node in it.
Example
Given the below binary tree:
1
/ \
2 3
return 4. (1->3)
思路
分治法。
以当前点开始的maxSum，取决于：
1：以当前点的左儿子为开始的maxSum是否大于0
2：以当前点的右儿子为开始的maxSum是否大于0
如果两者都小于0，那么以当前点开始的maxSum就是当前点的值。
public int maxPathSum2(TreeNode root) { // Write your code here if (root == null) { return 0; } int left = maxPathSum2(root.left); int right = maxPathSum2(root.right); if (Math.max(left, right) < 0) { return root.val; } return Math.max(left, right) + root.val; }
1. 我没问清每个Node是不不是都是正数，结果按照正数做的，然后⾯面试官
给了了个全是负数的例例⼦子，我就懵了了没想出来怎么解。以前做过但是好久没
看已经忘了了………后来补了了⼀一个限制条件简化题⽬目，就是如果node是负
数，可以跳过不不加这个node，然后应该是做出来了了
2. follow up是max subtree sum 和 sub-structure的sum
3. follow up是打印出path
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/124_Binary_Tree_Maximum_Path_Sum.java
Facebook惜败
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=454205
recursive function返回当前root下最大sum的path，然后用一个global max_sum_path去存最终答案。
