113. Path Sum II

class Solution 
{
private:
    vector<vector<int>> result;
    void pathSum(TreeNode *i_root, int sum, vector<int> pathValues)
    {
        if(!i_root) return;
        
        sum -= i_root->val;
        pathValues.push_back(i_root->val);
        if(!i_root->left && !i_root->right && sum == 0) result.push_back(pathValues);
        
        pathSum(i_root->left, sum, pathValues);
        pathSum(i_root->right, sum, pathValues);
    }
public:
    // vector<vector<int>> pathSum(TreeNode* root, int sum)
    vector<vector<int>> pathSum(TreeNode *i_root, int sum) 
    {
        pathSum(i_root, sum, vector<int>{});
        
        return result;
    }
};

// it is obvious the recursion version is slow
// since at every step, we could only handle one node, but we have to handle function stack, which is too heavy for one node's process
// so we should fix out this question by non recursion methord

class Solution 
{
public:
    // vector<vector<int>> pathSum(TreeNode* root, int sum)
    vector<vector<int>> pathSum(TreeNode *m_root, int sum) 
    {
        vector<int> pathValues;
        vector<vector<int>> result;
        stack<TreeNode *> parentNodes;
        
        for(auto iter = m_root; iter || !parentNodes.empty(); )
        {           
            if(iter) // at this condition, the node is valid, we continually go left
            {       
                sum -= iter->val;
                pathValues.push_back(iter->val);
                
                if(!iter->left && !iter->right && sum == 0) result.push_back(pathValues);
                
                parentNodes.push(iter);
                iter = iter->left;
            }
            else // at this condition, the node is invalid
            {
                iter = parentNodes.top(); // so we need to get a valid node
                parentNodes.pop();

                // no matter the last node locates at the left subtree or the right subtree
                // we will never go to the left tree, so we cut it
                iter->left = nullptr; 

                // if the iter->right is valid, we could to and check the right subtree
                // but at the same time, we must cut the right subtree, otherwise we will enter a dead loop
                // we go right, and come back to the current node, then we find the right subtree is valid, so we go right again
                // also, we have push the current node into the path, since there may have a valid answer at the right subtree
                if(iter->right)
                {
                    parentNodes.push(iter);
                    iter = iter->right;

                    parentNodes.top()->right = nullptr;
                }
                else 
                {
                    // if the iter->right is invalid, the current node is useless
                    // we just drop it, and hope go back to its parent to continue the process
                    sum += iter->val;
                    pathValues.pop_back();
                    iter = nullptr;
                }
            }
        }
        
        return result;
    }
};