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

[linqibin]

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

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

示例 1:

输入: [1,2,3]

   1
  / \
 2   3

输出: 6

示例 2:

这题做了好久啊。。。一开始没想通。每个节点都重新算一次所有子路径。
其实每个路径都只算一次就可以了啊。

思路：首先看到遍历树用递归就没跑了。
然后对于每个节点，最大路径和有几种情况：

1. 该节点是终点
2. 该节点+左子树
3. 该节点+右子树
4. 该节点+左子树+右子树（这种情况下就不能包含父节点了，即不return这种结果）
   根据这几种情况记录最大值就OK了

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
function maxPathSum(root) {

    if(!root) return;    
    
    let result = -Number.MAX_VALUE;

    result = Math.max(ergodic(root,0), result);
    
    function ergodic(node){
        if(node == null) return 0;

        let leftValue = ergodic(node.left);
        let rightValue = ergodic(node.right);

        let sum1 = node.val;
        let sum2 = node.val + leftValue;
        let sum3 = node.val + rightValue;
        let sum4 = node.val + leftValue + rightValue;

        let max = Math.max(sum1, sum2, sum3);
        if(sum4 > result) result = sum4;
        if(max > result) result = max;

        return max;
    }

    return result;
}