Commitbd9d3f6

applewjg

committed

PathSum

Change-Id: I9759d8750b60737cadb1ba0ca44479a8fdce7194

1 parent8cdafd1 commitbd9d3f6Copy full SHA for bd9d3f6

File tree

+41

-0

lines changed

+41

-0

lines changed

Lines changed: 41 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,41 @@`
	`1`	`+/*`
	`2`	`+ Author: Annie Kim, anniekim.pku@gmail.com`
	`3`	`+ Date: Apr 6, 2013`
	`4`	`+ Update: Jul 26, 2013`
	`5`	`+ Problem: Path Sum`
	`6`	`+ Difficulty: easy`
	`7`	`+ Source: http://www.leetcode.com/onlinejudge`
	`8`	`+ Notes:`
	`9`	`+ Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up`
	`10`	`+ all the values along the path equals the given sum.`
	`11`	`+`
	`12`	`+ For example:`
	`13`	`+ Given the below binary tree and sum = 22,`
	`14`	`+ 5`
	`15`	`+ / \`
	`16`	`+ 4 8`
	`17`	`+ / / \`
	`18`	`+ 11 13 4`
	`19`	`+ / \ \`
	`20`	`+ 7 2 1`
	`21`	`+ return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.`
	`22`	`+`
	`23`	`+ Solution: Recursion.`
	`24`	`+ */`
	`25`	`+/**`
	`26`	`+ * Definition for binary tree`
	`27`	`+ * public class TreeNode {`
	`28`	`+ * int val;`
	`29`	`+ * TreeNode left;`
	`30`	`+ * TreeNode right;`
	`31`	`+ * TreeNode(int x) { val = x; }`
	`32`	`+ * }`
	`33`	`+ */`
	`34`	`+publicclassSolution {`
	`35`	`+publicbooleanhasPathSum(TreeNoderoot,intsum) {`
	`36`	`+if (root ==null)returnfalse;`
	`37`	`+if (root.left ==null &&root.right ==null)returnsum ==root.val;`
	`38`	`+returnhasPathSum(root.left,sum -root.val) \|\|`
	`39`	`+hasPathSum(root.right,sum -root.val);`
	`40`	`+ }`
	`41`	`+}`

Comments

(0)