这个题的路径定义看起来不是很清晰,自己没啥思路,发现一个评论很有帮助。
摘抄如下:
不用看官方题解,那么复杂。 所有树的题目,都想成一颗只有根、左节点、右节点 的小树。然后一颗颗小树构成整棵大树,所以只需要考虑这颗小树即可。接下来分情况, 按照题意:一颗三个节点的小树的结果只可能有如下6种情况:
好了,分析上述6种情况, 只有 2,3,4 可以向上累加,而1,5,6不可以累加(这个很好想,情况1向上累加的话,必然出现分叉,情况5和6直接就跟上面的树枝断开的,没法累加),所以我们找一个全局变量存储 1,5,6这三种不可累加的最大值, 另一方面咱们用遍历树的方法求2,3,4这三种可以累加的情况。 最后把两类情况得到的最大值再取一个最大值即可。
自己实现JavaScript版本
/**
* @param {TreeNode} root
* @return {number}
*/
var maxPathSum = function (root) {
let max1 = Number.NEGATIVE_INFINITY;
let max2 = Number.NEGATIVE_INFINITY;
const helper = (node) => {
if (!node) {
return Number.NEGATIVE_INFINITY;
}
let sum = node.val;
let l = helper(node.left);
let r = helper(node.right);
let max = Math.max(sum, sum + l, sum + r);
max1 = Math.max(max1, max);
max2 = Math.max(max2, sum + l + r, l, r);
return max;
};
helper(root);
return Math.max(max1, max2);
};