Path Sum 12 ms easy to understand


  • 0
    P
    class Solution {
    public:
    
        using Elem = pair<TreeNode *, int>;
        using Stack = stack<Elem>;
    
        bool hasPathSum(TreeNode* root, int sum) {
            
            if(!root)
                return false;
        
            Stack pool;
            pool.push(Elem(root, root->val));
            
            while(!pool.empty())
            {
                auto p = pool.top();
                pool.pop();
                
                if(!p.first->left && !p.first->right && p.second == sum)
                    return true;
                
                if(p.first->left)
                {
                    auto nsum = p.first->left->val + p.second;
                    pool.push(Elem(p.first->left, nsum));
                }
                
                if(p.first->right)
                {
                    auto nsum = p.first->right->val + p.second;
                    pool.push(Elem(p.first->right, nsum));
                }
            }
            
            return false;
        }
    };

Log in to reply
 

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