129. Sum Root to Leaf Numbers

class Solution 
{
public:
    // int sumNumbers(TreeNode* root)
    int sumNumbers(TreeNode *i_root) 
    {
        int result = 0;        
        string pathValues;
        stack<TreeNode *> parentNodes;
        
        for(auto iter = i_root; iter || !parentNodes.empty(); )
        {         
            cout <<pathValues <<endl;
            if(iter) // at this condition, the node is valid, we continually go left
            {       
                pathValues.push_back('0' + iter->val);
                
                if(!iter->left && !iter->right) result += stoi(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
                    pathValues.pop_back();
                    iter = nullptr;
                }
            }
        }
        
        return result;
    }
};

class Solution 
{
private:
    int sumNumbers(TreeNode *i_root, int baseNumber)
    {
        if(!i_root) return 0;
        
        int newBaseNumber = baseNumber * 10 + i_root->val;
        
        if(!i_root->left && !i_root->right) return newBaseNumber;
        
        return sumNumbers(i_root->left, newBaseNumber) + sumNumbers(i_root->right, newBaseNumber);
    }
public:
    // int sumNumbers(TreeNode* root)
    int sumNumbers(TreeNode *i_root) 
    {
        return sumNumbers(i_root, 0);
    }
};