124. Binary Tree Maximum Path Sum - jiejackyzhang/leetcode-note GitHub Wiki

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example:

Given the below binary tree,

       1
      / \
     2   3

Return 6.

解题思路为postorder traversal。 当遍历到某个node时，得到左子树和右子树的max sum，若path只从一边上来，则还能继续上升到上一层level。 因此

curMax of this level: max(node's val v, v+left, v+right)
maxSum: max(maxSum, curMax, v+left+right)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    private int maxSum;
    
    public int maxPathSum(TreeNode root) {
        if(root == null) return 0;
        maxSum = root.val;
        postOrder(root);
        return maxSum;
    }
    
    private int postOrder(TreeNode node) {
        if(node == null) return 0;
        int left = postOrder(node.left);
        int right = postOrder(node.right);
        int curMax = Math.max(node.val, Math.max(node.val+left, node.val+right));
        maxSum = Math.max(maxSum, Math.max(curMax, node.val+left+right));
        return curMax;
    }
}