LeetCode/Path Sum.java at master · zhuchenchen97/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        //recursion
        if(root==null)
            return false;
        if(root.left==null && root.right==null && root.val==sum)
            return true;
        return (hasPathSum(root.left, sum-root.val)||hasPathSum(root.right, sum-root.val));

        //iteration
//         if(root==null)
//             return false;

//         Stack<TreeNode> stack  = new Stack<>();

//         while(!stack.isEmpty()  || root != null){
//             while(root!=null){
//                 sum = sum - root.val;
//                 stack.push(root);
//                 root=root.left;
//             }

// 		   if (sum == 0 && stack.peek().right == null && stack.peek().left == null) {
// 			return true;
// 		   }


//             while(!stack.isEmpty() && stack.peek().right == root){
//                root = stack.pop();
//                 sum = sum+root.val;
//             }

//             root = stack.isEmpty() ? null : stack.peek().right;
//         }
//         return false;
   }
}