[LintCode] 475 Binary Tree Maximum Path Sum II 解题报告

Description
Given a binary tree, find the maximum path sum from root.

The path may end at any node in the tree and contain at least one node in it.



Example
Given the below binary tree:

  1
 / \
2   3
return 4. (1->3)



思路
分治法。
以当前点开始的maxSum，取决于：
1：以当前点的左儿子为开始的maxSum是否大于0
2：以当前点的右儿子为开始的maxSum是否大于0

如果两者都小于0，那么以当前点开始的maxSum就是当前点的值。



Code

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root the root of binary tree.
     * @return an integer
     */
    public int maxPathSum2(TreeNode root) {
        // Write your code here
        
        if (root == null) {
            return 0;
        }
        
        int left = maxPathSum2(root.left);
        int right = maxPathSum2(root.right);
        
        if (Math.max(left, right) < 0) {
            return root.val;
        }
        
        return Math.max(left, right) + root.val;
    }
}