C++ both recursive and iterative


  • 0
    X
    class Solution {
    public:
        // iterative solution, post-order travel
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            stack<TreeNode*> st;
            TreeNode* cur = root;
            TreeNode* pre = NULL;
            vector<int> path;
            vector<vector<int>> ans;
            int curSum = sum;
            while(!st.empty() || cur != NULL){
                if(cur != NULL){
                    st.push(cur);
                    path.push_back(cur->val);
                    curSum -= cur->val;
                    if(cur->left == NULL && cur->right == NULL && curSum == 0){
                        ans.push_back(path);
                    }
                    cur = cur->left;
                }else{
                    TreeNode* top = st.top();
                    if(pre == top->right || top->right == NULL){
                        st.pop();
                        path.pop_back();
                        curSum += top->val;
                        pre = top;
                    }else{
                        cur = top->right;
                    }
                }
            }
            return ans;
        }
        // recursive solution
        /*
        void backtrack(TreeNode* cur, vector<int>& path, int sum, vector<vector<int>>& ans){
            if(cur == NULL){
                return;
            }
            path.push_back(cur->val);
            if(cur->left == NULL && cur->right == NULL){
                if(sum == cur->val){
                    ans.push_back(path);
                }
            }
            backtrack(cur->left, path, sum - cur->val, ans);
            backtrack(cur->right, path, sum - cur->val, ans);
            path.pop_back();
        }
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int>> ans;
            vector<int> path;
            backtrack(root, path, sum, ans);
            return ans;
        }
        */
    };

Log in to reply
 

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