Commitdaa7898

committed

Lintcode/src/chapter3_binary_tree_and_divide_and_conquer/BinaryTreeMaximumPathSum.java

1 parentff7777f commitdaa7898Copy full SHA for daa7898

File tree

+49

-0

lines changed

Lintcode/src/chapter3_binary_tree_and_divide_and_conquer
- BinaryTreeMaximumPathSum.java

+49

-0

lines changed

Lines changed: 49 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,49 @@`
	`1`	`+packagechapter3_binary_tree_and_divide_and_conquer;`
	`2`	`+`
	`3`	`+importclasses.TreeNode;`
	`4`	`+`
	`5`	`+publicclassBinaryTreeMaximumPathSum {`
	`6`	`+`
	`7`	`+//used the approach that jiuzhang officially explained, pretty cool!`
	`8`	`+//create a new class to store two pieces of information, this makes things a lot easier!`
	`9`	`+`
	`10`	`+/**`
	`11`	`+ * @param root: The root of binary tree.`
	`12`	`+ * @return: An integer.`
	`13`	`+ */`
	`14`	`+publicintmaxPathSum(TreeNoderoot) {`
	`15`	`+returndfs(root).maxPath;`
	`16`	`+ }`
	`17`	`+`
	`18`	`+ResultTypedfs(TreeNoderoot){`
	`19`	`+//exit`
	`20`	`+if(root ==null){`
	`21`	`+returnnewResultType(0,Integer.MIN_VALUE);`
	`22`	`+ }`
	`23`	`+`
	`24`	`+//divide`
	`25`	`+ResultTypeleft =dfs(root.left);`
	`26`	`+ResultTyperight =dfs(root.right);`
	`27`	`+`
	`28`	`+//conquer`
	`29`	`+intsinglePath =Math.max(left.singlePath,right.singlePath) +root.val;`
	`30`	`+singlePath =Math.max(0,singlePath);`
	`31`	`+`
	`32`	`+intmaxPath =Math.max(left.maxPath,right.maxPath);`
	`33`	`+maxPath =Math.max(maxPath,left.singlePath +right.singlePath +root.val);`
	`34`	`+`
	`35`	`+`
	`36`	`+returnnewResultType(singlePath,maxPath);`
	`37`	`+`
	`38`	`+ }`
	`39`	`+`
	`40`	`+classResultType {`
	`41`	`+intmaxPath;`
	`42`	`+intsinglePath;`
	`43`	`+ResultType(intsinglePath,intmaxPath){`
	`44`	`+this.maxPath =maxPath;`
	`45`	`+this.singlePath =singlePath;`
	`46`	`+ }`
	`47`	`+ }`
	`48`	`+`
	`49`	`+}`

Comments

(0)