My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxPathSum(TreeNode root) {
int[] max = new int[1];
max[0] = Integer.MIN_VALUE;
findMax(root, max);
return max[0];
}
private int findMax(TreeNode root, int[] max) {
if (root == null)
return 0;
int left = findMax(root.left, max);
int right = findMax(root.right, max);
int curr = Math.max(root.val, Math.max(root.val + left, root.val + right));
max[0] = Math.max(max[0], Math.max(curr, left + root.val + right));
return curr;
}
}
My test result:
这道题目需要仔细分析。而我没有怎么分析，就直接开始做了。等到认识到这道题目复杂性的时候，脑子已经乱了，所以网上看了答案，才写出来。
首先，针对上篇文章，我说的，除了容器，其他的，形参是无法改变实参的。
所以在C++中发明了引用，可以通过形参改变实参。但是Java中没有啊，怎么办。
只能传入容器，然后修改容器中的值，从而达到这个效果。
比如这道题目，如果光传入一个 int max; 是毫无作用的，
所以，传入了 int[] max = new int[1];
里面只放一个元素，但是他是存放在容器中的，他的改变，可以影响到外面的实参。
这个办法虽然笨，但是的确好用。
接下来说这道题目。
一个结点一共有四种取值方式，如下：
所以，必须采用bottom-up 的做法，先递归，再总结，post-order
pre-order -> top-down
post-order -> bottom-up
in-order -> ?
level-order -> bfs
从最底层开始，算出这四种方式的值，取最大值，然后更新进max[0]
同时，可以发现， #1, #2, #3 是属于第一种类型的，也就是从一个结点出发往下走，起点总是root
而#4则是第二种类型，起点并不是root。
所以，上一层的结点，也就是1结点的父亲节点，它是需要#1,#2,#3 这三种遍历方式的最大值的。
如果你担心，子节点的值，比如结点2的值,可能大于#1,但是传入上层的，却是#1.
那么这种担心是多余的。
其实我们在做两件事。
更新max， 如果结点2更大，那么，他的值早就被更新到max里面去了。
第二件事，就是不断地给上层建筑提供第一种类型的后代结点取值。使得他可以进行属于他的四种遍历，然后以此类推。
整个算法很简洁，不得不佩服。
下面提供参考的两篇博文。
http://bangbingsyb.blogspot.com/2014/11/leetcode-binary-tree-maximum-path-sum.html
http://www.programcreek.com/2013/02/leetcode-binary-tree-maximum-path-sum-java/
另外，这道题目的BST条件，似乎没什么用。因为如果全是负数，BST也没帮助了。
**
总结：
pre-order -> top-down
post-order -> bottom-up
in-order -> ?
level-order -> bfs
做一道题目，尤其是hard，一定要事先分析好，他有几种变化形式！
**
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null)
return 0;
dfs(root);
return max;
}
private int dfs(TreeNode root) {
if (root == null)
return 0;
int left = dfs(root.left);
int right = dfs(root.right);
int curr = root.val;
int cmp = Math.max(left + curr, Math.max(right + curr, curr));
max = Math.max(max, Math.max(cmp, left + curr + right));
return cmp;
}
}
没能一遍过。有点浮躁。虽然一开始思路是对的。
对于 到某个结点为止的最大值，可以是
- 结点本身
- 结点 + dfs(left child)
- 结点 + dfs(right child)
- 结点 + dfs(left child) + dfs(right child)
这里可以找出最大值。
然后，返回的时候，这里我犯错了。
他必须是一条路径，所以只能返回 1 2 3 情况下的最大值。
这道题目让我想起了两道题目，
Maximum Product Subarray -
http://www.jianshu.com/p/e1456b90c819Maximum Subarray -
http://www.jianshu.com/p/ac172786c4ab
他们也是，当前的最大值，
- 当前值
- 当前值 + 过去值
- 过去值
返回的是情况1 2 下的最大值。这样才能保证连续。
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
int ret = helper(root);
max = Math.max(max, ret);
return max;
}
private int helper(TreeNode root) {
if (root.left == null && root.right == null) {
max = Math.max(max, root.val);
return root.val;
}
else if (root.left == null || root.right == null) {
int temp = (root.left == null ? helper(root.right) : helper(root.left));
max = Math.max(max, Math.max(temp, root.val));
return Math.max(root.val, temp + root.val);
}
else {
int left= helper(root.left);
int right = helper(root.right);
max = Math.max(max, Math.max(left + root.val + right, Math.max(root.val, Math.max(left, right))));
return Math.max(root.val, Math.max(left, right) + root.val);
}
}
}
做了半小时才做出来。还是考虑的太不仔细了。
然后有些情况完全没必要重复比较。
Anyway, Good luck, Richardo! -- 08/28/2016
