[124] 二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1：

输入：[1,2,3]

输出：6

示例 2：

输入：[-10,9,20,null,null,15,7]

输出：42

这道题实际上是一个考察二叉树后序遍历逻辑的简单算法题。

我们注意到，想要获取到最大路径，则必须从下向上取值的所经过的路径都取最优即可。恰好二叉树的后序遍历就是从下向上遍历的，因此很容易想到解法。

我们最下层节点完成计算当前的最大路径和，并更新全局最优路径和，然后返回当前节点的最优路径值即可。

需要注意的是，这个最优路径值要是仍为负数的话，则需要置为0，视作舍弃包括该节点下的所有路径，从上一个节点作为起始点开始记录最优路径和。

边界条件理解清楚了后，问题就迎刃而解了。

var maxPathSum = function(root) {
  let res = -Number.MAX_VALUE;
  traverse(root);
  return res;

  function traverse(root) {
    if (!root) return 0;

    const left = traverse(root.left);
    const right = traverse(root.right);

    // 进行后序遍历处理

    // 当前最大路径和
    res = Math.max(res, left + right + root.val);

    // 当前的最大路径值，如果值为负数，则设为0，表示直接不取该节点，从上一个节点出发为更优
    return Math.max(0, left + root.val, right + root.val);
  }
};