9ms C++ iterative solution


  • 0
    S

    It's just an experiment to simulate function calling using stack, each frame is an pair<TreeNode*, int>, the first is the current root node, the second is the indicator of the return position:

        vector<vector<int>> ans;
        vector<int> v;
        int curr=0;
        if (root) {
            v.push_back(root->val);
            stack<pair<TreeNode*, int>> s;
            s.push(make_pair(root, 0));
            while (s.size()) {
                auto & f=s.top();
                switch (f.second) {
                    case 0:
                        curr+=f.first->val;
                        //printf("entering frame %d, curr=%d, status=%d\n", f.first->val, curr, f.second);
                        if (curr==sum&&!f.first->left&&!f.first->right) {
                            ans.push_back(v);
                            curr-=f.first->val;
                            s.pop();
                            continue;
                        }
                        f.second=1;
                        break;
                    case 1:
                        if (f.first->left) {
                            f.second=2;
                            v.push_back(f.first->left->val);
                            s.push(make_pair(f.first->left, 0));
                            continue;
                        }
                        f.second=3;
                        break;
                    case 2:
                        v.pop_back();
                        f.second=3;
                        break;
                    case 3:
                        if (f.first->right) {
                            f.second=4;
                            v.push_back(f.first->right->val);
                            s.push(make_pair(f.first->right, 0));
                            continue;
                        }
                        f.second=5;
                        break;
                    case 4:
                        v.pop_back();
                    case 5:
                        curr-=f.first->val;
                        s.pop();
                        break;
                }
            }
        }
        return ans;
    }

Log in to reply
 

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