My Path Sum with two deques-16ms


  • 0
    L

    bool hasPathSum(TreeNode* root, int sum) {
    int size;
    deque<TreeNode*> deq;
    deque<int> stack;
    if (!root) {
    return false;
    }
    deq.push_back(root);
    stack.push_back(root->val);
    if (!root->left && !root->right && root->val == sum) {
    return true;
    }

        while (1)
        {
            if (stack.empty()) {
                return false;
            }
            for (int i = 0; i < stack.size(); ++i)
            {
                if (stack[i] == sum && deq[i]->left == NULL && deq[i]->right == NULL)
                {
                    return true;
                }
            }
            size = deq.size();
            for (int i = 0; i < size; ++i)
            {
                if (deq[0]->left) {
                    stack.push_back(deq[0]->left->val + stack[0]);
                    deq.push_back(deq[0]->left);
                }
                if (deq[0]->right) {
                    stack.push_back(deq[0]->right->val + stack[0]);
                    deq.push_back(deq[0]->right);
                }
                deq.pop_front();
                stack.pop_front();
            }
        }
    }

Log in to reply
 

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