Commitc4271e5

applewjg

committed

Binary Tree Maximum Path Sum

Change-Id: I18d0bd0ddbed9517302aa674bb75c18b478395b1

1 parentca1c5dc commitc4271e5Copy full SHA for c4271e5

File tree

+43

-0

lines changed

+43

-0

lines changed

Lines changed: 43 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,43 @@`
	`1`	`+/*`
	`2`	`+ Author: Andy, nkuwjg@gmail.com`
	`3`	`+ Date: Jan 28, 2015`
	`4`	`+ Problem: Binary Tree Maximum Path Sum`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: https://oj.leetcode.com/problems/binary-tree-maximum-path-sum/`
	`7`	`+ Notes:`
	`8`	`+ Given a binary tree, find the maximum path sum.`
	`9`	`+ The path may start and end at any node in the tree.`
	`10`	`+ For example:`
	`11`	`+ Given the below binary tree,`
	`12`	`+ 1`
	`13`	`+ / \`
	`14`	`+ 2 3`
	`15`	`+ Return 6.`
	`16`	`+`
	`17`	`+ Solution: Recursion...`
	`18`	`+ */`
	`19`	`+`
	`20`	`+/**`
	`21`	`+ * Definition for binary tree`
	`22`	`+ * public class TreeNode {`
	`23`	`+ * int val;`
	`24`	`+ * TreeNode left;`
	`25`	`+ * TreeNode right;`
	`26`	`+ * TreeNode(int x) { val = x; }`
	`27`	`+ * }`
	`28`	`+ */`
	`29`	`+publicclassSolution {`
	`30`	`+publicintmaxPathSum(TreeNoderoot) {`
	`31`	`+int[]res =newint[1];`
	`32`	`+res[0] =Integer.MIN_VALUE;`
	`33`	`+maxPathSumRe(root,res);`
	`34`	`+returnres[0];`
	`35`	`+ }`
	`36`	`+intmaxPathSumRe(TreeNoderoot,int[]res) {`
	`37`	`+if (root ==null)return0;`
	`38`	`+intleft =maxPathSumRe(root.left,res);`
	`39`	`+intright =maxPathSumRe(root.right,res);`
	`40`	`+res[0] =Math.max(res[0],root.val +Math.max(left,0) +Math.max(right,0));`
	`41`	`+returnMath.max(root.val,root.val +Math.max(left,right));`
	`42`	`+ }`
	`43`	`+}`

Comments

(0)