leetcode_practice/112-path-sum.cpp at main · ssarmin/leetcode_practice · 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

https://leetcode.com/problems/path-sum/description/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root)
            return false;
        stack<pair<TreeNode*, int>> s;
        s.push({root, 0});

        while(!s.empty()){
            root = s.top().first;
            int sum = s.top().second + root->val;
            s.pop();
            bool flag = true;
            if(root->left){
                flag = false;
                s.push({root->left, sum});
            }
            if(root->right){
                flag = false;
                s.push({root->right, sum});
            }
            if(flag){
                if(targetSum == sum)
                    return true;
            }
        }

        return false;
    }
};


class Solution {
public:
    bool check(TreeNode* root, int currSum, int targetSum){
        if(root == NULL){
            return (currSum == targetSum);
        }
        if(root->left && root->right)
            return check(root->left, currSum+root->val, targetSum) || check(root->right, currSum+root->val, targetSum);
        if(root->left && !root->right)
            return check(root->left, currSum+root->val, targetSum);
        if(!root->left && root->right)
            return check(root->right, currSum+root->val, targetSum);
        return (currSum+root->val == targetSum);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root)
            return false;
        if(root->left && root->right)
            return check(root->left, root->val, targetSum) || check(root->right, root->val, targetSum);
        if(root->left && !root->right)
            return check(root->left, root->val, targetSum);
        if(!root->left && root->right)
            return check(root->right, root->val, targetSum);
        return (root->val == targetSum);
    }
};


// Extra testcases:
// [10,2,11,0]
// 12
// [1,2]
// 1
// [1]
// 1
// [5,4,8,11,null,13,4,7,2,null,null,null,1]
// 22
// [1,2,3]
// 5
// [0]
// 0
// [1,2]
// 1
// [1,2]
// 2
// [-2,null,-3]
// -5
// [-2,null,-3]
// 0
// [8,9,-6,null,null,5,9]
// 7
// [1]
// 0