C++ 12ms recursive & iterative solutions


  • 2
    Z
    class Solution {
    public:
    bool hasPathSum(TreeNode* root, int sum) {
        //return solution1(root, sum);        //recursive
        return solution2(root, sum);        //iterative
    }
    private:
    bool solution1(TreeNode *n, int sum){
        if(!n) return false;
        if(!n->left && !n->right) return sum - n->val == 0;
        return solution1(n->left, sum - n->val) || solution1(n->right, sum - n->val);
    }
    bool solution2(TreeNode *n, int sum){
        if(!n) return false;
        stack<TreeNode *> st;
        TreeNode *cur = n, *pre;
        while(cur || !st.empty()){
            while(cur){
                st.push(cur);
                sum -= cur->val;
                cur = cur->left;
            }
            cur = st.top();
            if(!cur->left && !cur->right && !sum) return true;
            if(cur->right && pre != cur->right) cur = cur->right;
            else{
                st.pop();
                sum += cur->val;
                pre = cur;
                cur = NULL;
            }
        }
        return false;
    }
    };

Log in to reply
 

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