求二叉樹的最大路徑和，路徑含任意起始節(jié)點(diǎn)和任意終止節(jié)點(diǎn)。

遞歸實(shí)現(xiàn)

• Runtime: 104 ms, faster than 51.09%
• Memory Usage: 48.7 MB, less than 30.83%

var maxPathSum = function(root) {
    let res = -Infinity
    function recursive(root) {
        if (root === null) return 0
        let left = Math.max(0, recursive(root.left))
        let right = Math.max(0, recursive(root.right))
        res = Math.max(res, root.val + left + right)
        return root.val + Math.max(left, right)
    }
    recursive(root)
    return res
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var res = - Math.pow(2, 32) 
var maxPathSum = function(root) {
    subPathSum(root)
    return res
};
var subPathSum = function(root){
    if(root === null) return 0
    var left = Math.max(0, subPathSum(root.left))
    var right = Math.max(0, subPathSum(root.right))
    res = Math.max(res, root.val + left + right)
    return root.val + Math.max(left, right)
}

java實(shí)現(xiàn)，faster than 96%

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        //post order traversal
       maxPathSumCalculate(root);
       return ans;
    }
    
    public int maxPathSumCalculate(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(0,maxPathSumCalculate(root.left));
        int right = Math.max(0,maxPathSumCalculate(root.right));
        ans = Math.max(ans, root.val + left + right);
        return root.val + Math.max(left, right);
    }
}