Share my 9ms iterative C++ solution


  • 0
    S
    class Solution {
    public:
        bool hasPathSum(TreeNode* root, int sum) {
            bool result = false;
            if(!root) return result;
            stack<TreeNode*> stk;
            int tempsum = 0;
            TreeNode* cur = root, *pre = NULL;
            while(cur || !stk.empty()){
                while(cur){
                    stk.push(cur);
                    tempsum += cur->val;
                    pre = cur;
                    cur = cur->left;
                }
                cur = stk.top();
                if(!cur->left && !cur->right && tempsum == sum){
                    result = true;
                    break;
                }
                if(cur->right && pre != cur->right){
                    cur = cur->right;
                }
                else{
                    stk.pop();
                    tempsum -= cur->val;
                    pre = cur;
                    cur = NULL;
                }
            }
            return result;
        }
    };
    

Log in to reply
 

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