|
| 1 | +packageeasy; |
| 2 | + |
| 3 | +importclasses.TreeNode; |
| 4 | + |
| 5 | +/**112. Path Sum QuestionEditorial Solution My Submissions |
| 6 | +Total Accepted: 115095 |
| 7 | +Total Submissions: 360394 |
| 8 | +Difficulty: Easy |
| 9 | +Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. |
| 10 | +
|
| 11 | +For example: |
| 12 | +Given the below binary tree and sum = 22, |
| 13 | + 5 |
| 14 | + / \ |
| 15 | + 4 8 |
| 16 | + / / \ |
| 17 | + 11 13 4 |
| 18 | + / \ \ |
| 19 | + 7 2 1 |
| 20 | +return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.*/ |
| 21 | +publicclassPathSum { |
| 22 | +publicbooleanhasPathSum(TreeNoderoot,intsum) { |
| 23 | +if(root ==null)returnfalse; |
| 24 | +if(root.val ==sum &&root.left ==null &&root.right ==null)returntrue; |
| 25 | +returnhasPathSum(root.left,sum -root.val) ||hasPathSum(root.right,sum -root.val); |
| 26 | + } |
| 27 | + |
| 28 | +publicstaticvoidmain(String...strings){ |
| 29 | +PathSumtest =newPathSum(); |
| 30 | +// TreeNode root = new TreeNode(1); |
| 31 | +// root.left = new TreeNode(2); |
| 32 | +// int sum = 1; |
| 33 | + |
| 34 | +TreeNoderoot =newTreeNode(1); |
| 35 | +root.left =newTreeNode(-2); |
| 36 | +root.left.left =newTreeNode(1); |
| 37 | +root.left.right =newTreeNode(3); |
| 38 | +root.right =newTreeNode(-3); |
| 39 | +root.right.left =newTreeNode(-2); |
| 40 | +root.left.left.left =newTreeNode(-1); |
| 41 | +intsum =2; |
| 42 | +// 1 |
| 43 | +// / \ |
| 44 | +// -2 -3 |
| 45 | +// / \ / |
| 46 | +// 1 3 -2 |
| 47 | +// / |
| 48 | +// -1 |
| 49 | +System.out.println(test.hasPathSum(root,sum)); |
| 50 | + } |
| 51 | +} |