leetcode/112.path-sum.cpp at master · ndkaur/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
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
/*
 * @lc app=leetcode id=112 lang=cpp
 *
 * [112] Path Sum
 */
#include "bits/stdc++.h"
using namespace std;
#include "Tree.h"
#define deb(x) cout<<x<<endl;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int,int> pii;
#include "LinkedList.h"

void print(vi &out){
    for(auto x: out) cout<<x<<" ";
    cout<<endl;
}

// @lc code=start
/**
 * 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 sum) {
        if(!root) return false;
        sum=sum-root->val;
        if(sum==0 && !root->left && !root->right) // if is a leaf and sum equal to target
            return true;
        return hasPathSum(root->left,sum) || hasPathSum(root->right,sum);
    }
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root==NULL) return false;
        stack<pair<TreeNode *,int>> stk;
        stk.push({root,root->val});
        while(!stk.empty()){
            TreeNode *curr =stk.top().first;
            int tsum= stk.top().second;
            stk.pop();
            if(curr->left) stk.push({curr->left,tsum+curr->left->val});
            if(curr->right) stk.push({curr->right, tsum+curr->right->val});
            if(!curr->left && !curr->right && tsum==sum)
                return true;

        }
        return false;
    }
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        if(root->val ==sum && root->left==NULL && root->right==NULL) // after including the leaf value
            return true;
        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum- root->val);
    }
};


class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) return false;
        int sum = root->val;
        return f(root, sum, targetSum);
    }
    bool f(TreeNode* root, int sum, int& tar){
        if(!root) return false;
        if(sum==tar && root->left==NULL && root->right==NULL) // check if leaf node
            return true;
        bool left = root->left ? f(root->left, sum+root->left->val, tar) : 0;
        bool right = root->right ? f(root->right, sum+root->right->val, tar):0;
        return left || right;
    }
};
// @lc code=end

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    Solution sol;
    string s = "[]"; int sum =0;
    TreeNode* root = stringToTreeNode(s);
    bool out = sol.hasPathSum(root, sum); deb(out);
    return 0;
}