Binary Tree Maximum Path Sum II 475

Question

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)

Solution

水题，直接通d&c即可。唯一要注意的是题目要求至少有一个点，所以左右值先和0比较后再和root值相加。

代码如下：

/**
 * 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);

        return root.val + Math.max(0, Math.max(left, right));
    }
}