(Leet Code c++)Path Sum

112. Path Sum

Easy

3500644Add to ListShare

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

 

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true

Example 2:

Input: root = [1,2,3], targetSum = 5 Output: false

Example 3:

Input: root = [1,2], targetSum = 0 Output: false

 

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

주어진 이진 트리에서 리프노드까지의 합이 targetSum과 같은지 확인하는 문제.

 

BFS를 통해 답을 구할 수 있다.

root가 NULL이 아니라면 BFS 진행.

 

NULL이라면 false를 리턴해주면 된다.

 

--BFS

시작은 (root, 0)을 큐에 넣어 진행한다.

큐가 빌 때까지 반복.

만약 큐가 빌 때까지 true가 리턴되지 않는다면 조건을 만족하지 않기 때문에 false를 리턴하게 된다.

 

현재 노드를 나타내는 current와 현재까지의 합을 나타내는 sum이 큐에 있다.

왼쪽 자식 노드와 오른쪽 자식 노드가 모두 NULL이라면 리프 노드를 뜻하게 된다.

현재 노드가 리프 노드일 때 sum과 targetSum과 비교하여 같으면 true를 리턴.

같지 않다면 계속해서 BFS를 진행하게 된다.(큐가 빌 때까지 진행...)

 

리프 노드가 아니라면 왼쪽 자식 또는 오른쪽 자식 노드를 큐에 넣어 계속 진행하면 된다.

/**
 * 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) {
        queue<pair<TreeNode *, int>> q;
        
        if(root != NULL){
            q.push(make_pair(root, 0));
            
            while(!q.empty()){
                TreeNode * current = q.front().first;
                int sum = q.front().second;
                
                q.pop();
                
                if(current->left == NULL && current->right == NULL){
                    if(sum + current->val == targetSum){
                        return true;
                    }
                }
                
                if(current->left != NULL){
                    q.push(make_pair(current->left, sum + current->val));
                }
                
                if(current->right != NULL){
                    q.push(make_pair(current->right, sum + current->val));
                }
            }
        }
        
        return false;
    }
};