Binary Tree Maximum Path Sum 94

Question

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.

Solution

这题严格意义上应该属于D&C。singlePath表示以该点为root的子树从root出发能够取的最大path，maxPath表示以该点为root的子树中任意一点到任意一点能取的最大path。

对于每一个node，以该点为root的子树的最大path有两种可能：第一种为不经过该root的path，第二种为经过该root的path。对于第一种情况，最大path为root左边或者右边的最大path，第二种为左边的singlePath + 右边的singlePath＋root值。

singlePath的状态函数：max(max(root.left.singlePath, root.rigth.singlePath)+root.val,0)，表示若结果为负数，则可以不包含任何点

maxPathd的状态函数：max(root.left.maxPath, root.right.maxPath, root.left.singlePath + root.right.singlePath + root.val)，至少包含一个点。

代码如下：

/**
 * 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;
 *     }
 * }
 */
class ResultType{
    int singlePath;
    int maxPath;
    public ResultType(int singlePath, int maxPath){
        this.singlePath = singlePath;
        this.maxPath = maxPath;
    }
}

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
    public int maxPathSum(TreeNode root) {
        // write your code here
        ResultType r = helper(root);
        return r.maxPath;
    }

    public ResultType helper(TreeNode root){
        if(root == null){
            return new ResultType(0, Integer.MIN_VALUE);
        }

        ResultType left = helper(root.left);
        ResultType right = helper(root.right);
        //singlePath不一定至少包含一个node
        int s = Math.max(Math.max(left.singlePath, right.singlePath) + root.val, 0);

        int m = Math.max(left.maxPath, right.maxPath);
        m = Math.max(m, left.singlePath + right.singlePath + root.val);

        return new ResultType(s, m);
    }
}