Share my non-recursive solution


  • 3
    D

    post order

    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int>> result;
        if(root == NULL)
        {
            return result;
        }
        
        stack<TreeNode*> nodeStack;
        TreeNode *current = root;
        TreeNode *last = NULL;
        vector<int> set;
        int pathSum = 0;
        
        while(!nodeStack.empty() || current != NULL)
        {
            if(current == NULL)
            {
                TreeNode *node = nodeStack.top();
                
                if(node->right != NULL && last != node->right)
                {
                    current = node->right;   
                }
                else
                {
                    last = node;
                    nodeStack.pop();
                    set.pop_back();
                    pathSum -= node->val;
                }
            }
            else
            {
                nodeStack.push(current);
                set.push_back(current->val);
                pathSum += current->val;
                
                if(current->left == NULL && current->right == NULL && pathSum == sum)
                {
                    vector<int> row;
                        
                    for(int i =0;i<set.size();i++)
                    {
                        row.push_back(set[i]);
                    }
                    
                    result.push_back(row);
                }
                
                current = current->left;
            }
        }
        
        return result;
    }

Log in to reply
 

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