112. Path Sum

發表於 | 分類於

problem

solution

option 1 - dfs

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        // dfs
        // 終止條件
        if(!root ) return false;
        targetSum-=root->val;
        // 拜訪到葉子了
        if(!root->left && !root->right && targetSum == 0) return true;
        return hasPathSum(root->left, targetSum ) || hasPathSum(root->right, targetSum);
    }
};

option 2 - bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) return false;
        queue<pair<TreeNode*,int>> q;
        q.push({root, root->val});
        while(!q.empty()){
            auto [p, val] = q.front();
            q.pop();
            if(!p->left && !p->right && val == targetSum) return true;
            if(p->left) q.push({p->left, p->left->val+val});
            if(p->right) q.push({p->right, p->right->val + val});
        }
        return false;
    }
};