Last active
December 11, 2015 14:49
-
-
Save guolinaileen/4617013 to your computer and use it in GitHub Desktop.
Java doesn't allow to modify passed-in parameters. For this problem, we need to keep track two things during recursions: the max subpath sum and the current max sum for a given node. One way is to let the helper method return an array of two items; Another way is to pass in the current max as an array of one item.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Definition for binary tree | |
* public class TreeNode { | |
* int val; | |
* TreeNode left; | |
* TreeNode right; | |
* TreeNode(int x) { val = x; } | |
* } | |
*/ | |
public class Solution { | |
public int maxPathSum(TreeNode root) { | |
// Start typing your Java solution below | |
// DO NOT write main() function | |
ArrayList<Integer> list=new ArrayList<Integer>(); | |
list.add(Integer.MIN_VALUE); | |
find(root, list); | |
return list.get(0); | |
} | |
int find(TreeNode root, ArrayList<Integer> list) | |
{ | |
if(root==null) return 0; | |
int left=find(root.left, list); | |
int right=find(root.right, list); | |
int total=Math.max(root.val, Math.max(root.val+Math.max(left, right), root.val+left+right)); | |
list.add(0, Math.max(list.get(0), total)); | |
return Math.max(root.val, root.val+Math.max(left, right)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment