C++ iterative solution with one vector, 17ms


  • 0
    R

    Basically use a vector as a stack and do a standard in-order traversal. The reason to use vector is for easily backtracking. Instead of popping out a node from the stack before traversing its right child, I kept it in the "stack" with a mark so as to track the whole path.

    class Solution {
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int>> paths;
            if (!root) return paths;
            // vector element: {current node, {remainder from root till current node, mark whether this node has been visited}}
            vector<pair<TreeNode *, pair<int, int>>> st;   
            TreeNode * cur = root;
            int rs = sum;
            while (cur) {
                rs -= cur->val;
                st.push_back({cur, {rs, 0}});
                cur = cur->left;
            }
            while (!st.empty()) {
                auto& e = st.back(); 
                if (e.second.second == 1) {
                    st.pop_back();
                    continue;
                } else {
                    e.second.second = 1;
                }
                if (e.second.first == 0 && !e.first->left && !e.first->right) {
                    vector<int> inst;
                    for (auto it = st.begin(); it != st.end(); it++) inst.push_back(it->first->val);
                    paths.push_back(inst);
                }
                cur = e.first->right;
                rs = e.second.first;
                while (cur) {
                    rs -= cur->val;
                    st.push_back({cur, {rs, 0}});
                    cur = cur->left;
                }
            }
            return paths;
        }
    };

Log in to reply
 

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