[C++ BFS]just for practice


  • 0
    L

    we can use two queues, one deals with the pointers while the other stores the sum we get at each step, the code is not hard to understand:

    class Solution {
    public:
        bool hasPathSum(TreeNode* root, int sum) {
            if(!root)return false;
            queue<TreeNode*> q;
            queue<int> sum_q;
            q.push(root);//enqueue
            sum_q.push(root->val);//enqueue
            while(!q.empty()){
                TreeNode* p=q.front();
                int tot=sum_q.front();
                q.pop();//dequeue
                sum_q.pop();//dequeue        
                if(!(p->left)&&!(p->right)&&(sum==tot))
                    return true;
                if(p->left){
                    q.push(p->left);
                    sum_q.push(tot+p->left->val);
                }
                if(p->right){
                    q.push(p->right);
                    sum_q.push(tot+p->right->val);
                }
            }
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.