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

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

The path may start and end at any node in the tree.



Example
Given the below binary tree:

  1
 / \
2   3
return 6.



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

以当前节点为起点的maxSum就是1，2的最大值加上当前节点的值。

通过当前节点的maxSum就是1，2，以及当前节点的值相加。
在计算这个值的时候，维护一个全局的maxPathSum值，作为最后的答案。



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.
     */
     
    private int max = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        // write your code here
        helper(root);
        return max;
    }
    
    public int helper(TreeNode root) {
        if (root == null) return 0;
        
        int left = Math.max(helper(root.left), 0);
        int right = Math.max(helper(root.right), 0);
        
        max = Math.max(max, root.val + left + right);
        
        return root.val + Math.max(left, right);
    }
}