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

题意：

解题思路：

思路：
1. 递归计算左右子树的最大值，将它与0进行比较，如果大于才加上去，否则就舍去一边;
2. 按层级与左右子树三个值相加更新全局答案；
3. 返回左右子树比较大的那个子树的和[根节点+max(left, right)]

PHP代码实现：

class Solution {
    public $max = PHP_INT_MIN;
    /**
     * @param TreeNode $root
     * @return Integer
     */
    function maxPathSum($root) {
        if(empty($root)) return 0;
        $this->helper($root);
        return $this->max;
    }
    function helper($node) {
        if(empty($node)) return 0;
        $left = max($this->helper($node->left), 0);
        $right = max($this->helper($node->right), 0);
        //每一层最大值进行比较
        //求的过程中考虑包含当前根节点的最大路径
        $this->max = max($this->max, $node->val + $left + $right);
        //只返回包含当前根节点和左子树或者右子树的路径
        return $node->val + max($left, $right);
    }
}

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxInt(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}
func maxPathSum(root *TreeNode) int {
    maxResult := math.MinInt32
    var pathSum func(*TreeNode) int
    pathSum = func(curNode *TreeNode) int {
        if curNode == nil {
            return 0
        }
        left := maxInt(0, pathSum(curNode.Left))
        right := maxInt(0, pathSum(curNode.Right))
        maxResult = maxInt(maxResult, left + curNode.Val + right)
        return curNode.Val + maxInt(left, right)
    }
    _ = pathSum(root)
    return maxResult
}