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.
public class Solution { /** * @param root: The root of binary tree. * @return: An integer. */ int maxValue; public int maxPathSum(TreeNode root) { maxValue = Integer.MIN_VALUE; maxPathDown(root); return maxValue; } private int maxPathDown(TreeNode node) { if (node == null) return 0; int left = Math.max(0, maxPathDown(node.left)); int right = Math.max(0, maxPathDown(node.right)); maxValue = Math.max(maxValue, left + right + node.val); return Math.max(left, right) + node.val; } }
public class Solution { int max = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function if(root == null) return 0; dfs(root); return max; } public int dfs(TreeNode node){ if(node == null) return 0; int parent = node.val; int left = dfs(node.left); int right = dfs(node.right); if(left > 0) parent+= left; if(right > 0)parent+= right; max = Math.max(max,parent); int side = Math.max(left,right); return side>0 ? node.val + side: node.val; } }