124. 二叉树中的最大路径和

解题思路

粗略思路：从叶子节点开始，以贪心策略求得局部最大路径和，叶子节点计算完之后，回到父节点，再以同样的贪心策略求得局部最大路径和，重复该过程，显然这是二叉树的后序遍历。

技巧总结：

  • 假如以递归实现，思路上要从最深或次深一层的调用考虑要做的操作，先忽略上层调用；
  • 再考虑相邻两层之间要做的操作，最后多考虑几组这样的关系；

考虑：

  1. 由于要求最大路径和，那么节点值是负数就会让路径和变小，因此路径只取值为正数的节点；
  2. 次深一层调用，求以叶子节点为端点的路径的最大路径和，显然就是叶子节点本身；
  3. 再高一层，此时已经求得以子节点为端点的路径的最大路径和，此时要求父节点（当前节点）的最大路径和，则有：以左或右子节点为端点的路径 + 当前单个节点的路径；
  4. 每一层，由于已知左、右子节点为端点的路径的最大路径和，则还有一种路径：以左子节点为端点的路径 + 当前单个节点的路径 + 以右子节点为端点的路径；
  5. 每次计算路径和时，要更新一个全局变量maxSum以记录最大路径和；
  6. 最深一层调用，显然是叶子节点的左右空指针，为了保证其不影响叶子节点的路径和，返回0即可，此时次深一层调用的操作也变成了：以左或右子节点为端点的路径（0） + 当前单个节点的路径，完美；
  7. 每一层的行为都统一了，返回以当前节点为端点的最大路径和：计算并返回以左或右子节点为端点的路径（不存在则返回0） + 当前单个节点的路径；
  8. 每一层再加上一个额外的计算：以左子节点为端点的路径 + 当前单个节点的路径 + 以右子节点为端点的路径；
  9. 7中的返回值，结合1考虑，如果返回值是负数，则返回0，意思是不选择该路径；

注：约定一下，这种说法——“以叶子节点为端点的路径”的隐含一层意思是另一端点为后代某一节点；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {TreeNode} root
 * @return {number}
 */

var maxPathSum = function (root) {
    var maxSum = root.val;
    // 返回0可理解为不做选择
    (function maxPartialSum(root) {
        if (!root) return 0;

        const leftPartialSum = maxPartialSum(root.left);
        const rightPartialSum = maxPartialSum(root.right);
        // 后序遍历

        // 此时，以左、右孩子为端点的路径已求得局部最大和（局部最优），
        // 则当前单个节点的路径，左和右孩子为端点的路径，3者共同组成新路径；
        const partialSum = root.val + leftPartialSum + rightPartialSum;
        // 计算其局部和之后，更新到maxSum
        maxSum = Math.max(maxSum, partialSum);

        // 此处做出选择以取得局部最优（换句话说，要让该条路径的和最大）：
        // 当前单个节点的路径，左或右孩子为端点的路径，2者共同组成新路径，计算其局部和，
        // 如果是负数，由于加上一个负数一定会更小，因此返回0，表示抛弃该路径；
        const abc = root.val + Math.max(leftPartialSum, rightPartialSum);        
        return abc > 0 ? abc : 0;
    })(root)
    return maxSum;
};