*[Lintcode]Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

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

For example: Given the below binary tree,

1 / \ 2 3

Return 6.

先明确一下路径你给的定义：从根节点到树中某节点经过的分支。一共四种情况：

左子树的路径加上当前节点

右子树的路径加上当前节点

左右子树的路径加上当前节点（计算sum时需要考虑。计算path时，不考虑此情况。）

只有当前节点

public class Solution { /** * @param root: The root of binary tree. * @return: An integer. */ static int max = Integer.MIN_VALUE; //负值在路径上时没有关系，因为计算的是sum public int maxPathSum(TreeNode root) { helper(root); return max; } int helper(TreeNode root) { if(root == null) return 0; int res = root.val; int left = 0; int right = 0; if(root.left != null) { left = helper(root.left); if(left > 0) res += left; } if(root.right != null) { right = helper(root.right); if(right > 0) res += right; } if(res > max) max = res; return Math.max(root.val, Math.max(root.val + left, root.val + right)); } }