原文

这个题的路径定义看起来不是很清晰,自己没啥思路,发现一个评论很有帮助。

摘抄如下:

不用看官方题解,那么复杂。 所有树的题目,都想成一颗只有根、左节点、右节点 的小树。然后一颗颗小树构成整棵大树,所以只需要考虑这颗小树即可。接下来分情况, 按照题意:一颗三个节点的小树的结果只可能有如下6种情况:

  1. 根 + 左 + 右
  2. 根 + 左
  3. 根 + 右

好了,分析上述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);
};

上一篇 下一篇