C++ non-recursive solution


  • 0
    B
    class Solution {
    public:
        vector<int> savepath(stack<TreeNode*> stk){
            stack<TreeNode*> tmp;
            vector<int> v;
            TreeNode * node;
            while(!stk.empty()){
                node = stk.top();
                stk.pop();
                v.insert(v.begin(), node->val);
            }
            return v;
        }
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int>> result;
            if(!root) return result;
            TreeNode *cur = root, *pre = NULL;
            stack<TreeNode*> stk;
            int path_sum = 0;
            while(cur || !stk.empty()){
                while(cur){
                    stk.push(cur);
                    path_sum += cur->val;
                    cur = cur->left;
                }
                cur = stk.top();
                if(!cur->left && !cur->right && path_sum == sum){
                    vector<int> v = savepath(stk);
                    result.push_back(v);
                }
                if(cur->right && pre != cur->right){
                    cur = cur->right;
                }else{
                    stk.pop();
                    path_sum -= 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.