LeetCode-124:Binary Tree Maximum Path Sum
题目
- 很高兴leetcode上点击量最高的解法和我一样,而且这题难度也就Medium吧
- 我真是提交了n多遍才理解了这题什么意思:在二叉树中,从一个节点开始,左右可以向下延伸,但不能分叉,可以说呈倒V字形,这样一个结构,这个结构可以从任何点开始,可以不包括root,可以只有一个节点,可以没有左分支或者右分支,计算出上边结构的所有节点val的和,要求找出一个结构,使得和最大
思路
- 先对节点做一个认识:一个节点如果在一个这样的倒V字形结构中,那么就有两种情况
- 第一,此节点就是这个结构的根节点,那么此时该结构的和就是sum=val+left+right,当然,如果left或者right小于0的话就不加了
- 第二,此节点不是根节点,那么他需要提供一个最大的和给他的父节点,这个和可能是val,可能是val+left,可能是val+right,但不会是val+left+right,因为左右分支不能分叉
- 程序整体的结构已经很明显了,是一个二叉树的后续遍历,两点需要注意,使用参数或者全局变量max来记录出现的所有倒V字形结构的sum中的最大值,这个值是最后需要返回的结果,再用返回值返回上边列举的第二种情况的值,提供给父节点使用
好像就这么简单,实现起来也很简单,下边是leetcode上一个挺精简的解法,最下边是我自己的代码
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) {
List<Integer> max = new ArrayList<>();
max.add(-Integer.MAX_VALUE);
findMax(root, max);
return max.get(0);
}
public static int findMax(TreeNode root, List<Integer> max) {
int ret = root.val;
int left = -1;
int right = -1;
if (root.left != null) {
left = findMax(root.left, max);
}
if (root.right != null) {
right = findMax(root.right, max);
}
int tmp = ret + (left > 0 ? left : 0) + (right > 0 ? right : 0);
if (tmp > max.get(0))
max.set(0, tmp);
if (left > 0 || right > 0) {
ret += left > right ? left : right;
}
return ret;
}
还没有评论,来说两句吧...