Commitff7777f

committed

Lintcode/src/chapter3_binary_tree_and_divide_and_conquer/BinaryTreeMaximumPathSumII.java

1 parent49cfd42 commitff7777fCopy full SHA for ff7777f

File tree

+35

-0

lines changed

Lintcode/src/chapter3_binary_tree_and_divide_and_conquer
- BinaryTreeMaximumPathSumII.java

+35

-0

lines changed

Lines changed: 35 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,35 @@`
	`1`	`+packagechapter3_binary_tree_and_divide_and_conquer;`
	`2`	`+`
	`3`	`+importclasses.TreeNode;`
	`4`	`+`
	`5`	`+publicclassBinaryTreeMaximumPathSumII {`
	`6`	`+`
	`7`	`+/**`
	`8`	`+ * @param root the root of binary tree.`
	`9`	`+ * @return an integer`
	`10`	`+ */`
	`11`	`+intmax =Integer.MIN_VALUE;`
	`12`	`+publicintmaxPathSum2(TreeNoderoot) {`
	`13`	`+// Write your code here`
	`14`	`+if(root ==null)return0;`
	`15`	`+returndfs(root,0,max);`
	`16`	`+ }`
	`17`	`+`
	`18`	`+intdfs(TreeNoderoot,intcurr,intmax){`
	`19`	`+curr +=root.val;`
	`20`	`+max =Math.max(max,curr);`
	`21`	`+intleftMax =max,rightMax =max;`
	`22`	`+if(root.left !=null)leftMax =dfs(root.left,curr,max);`
	`23`	`+if(root.right !=null)rightMax =dfs(root.right,curr,max);`
	`24`	`+returnMath.max(Math.max(leftMax,rightMax),max);`
	`25`	`+ }`
	`26`	`+`
	`27`	`+publicstaticvoidmain(String...strings){`
	`28`	`+BinaryTreeMaximumPathSumIItest =newBinaryTreeMaximumPathSumII();`
	`29`	`+TreeNoderoot =newTreeNode(1);`
	`30`	`+root.left =newTreeNode(2);`
	`31`	`+root.right =newTreeNode(3);`
	`32`	`+System.out.print(test.maxPathSum2(root));`
	`33`	`+ }`
	`34`	`+`
	`35`	`+}`

Comments

(0)