Iterative C++ solution using stack (similar to postorder traversal)


  • 6
    N

    Iterative C++ solution using postorder traversal to treat the nodes

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int sumNumbers(TreeNode* root) {
            
            stack<TreeNode*> nodes;
            if (!root)
             return 0;
             
            int total = 0;
            int current = 0;
            TreeNode* last = nullptr;
            while (root || !nodes.empty())
            {
                if (root)
                {
                    nodes.push(root);
                    current *= 10;
                    current += root->val;
                    root = root->left;
                }
                else 
                {
                    root = nodes.top();
                    if (root->right && root->right != last)
                    {
                        root = root->right;
                    }
                    else 
                    {
                         nodes.pop();
                         last = root;
                         // only add sum of leaf node
                         if (root->right == nullptr && root->left == nullptr)
                            total += current;
                         current /= 10;
                         root = nullptr;
                    }
                }
              }
            
             return total;
        }
    };

  • 0
    L

    Hey Nergal, I do not quite understand what the last is used for here? Can you provide more explanation? Moreover, what is the condition for current /= 10?


  • 0
    N

    Hello,
    the last is here to indicate the right sub-tree has already been checked or not. We only want to add a right sub-tree once. You could probably do this differently.
    As I only pop when reaching a leaf, when I go up the tree I encounter some already checked node, I keep them in the tree to be able to perform the "current" division by 10.

    What do you mean by "current /= 10" condition ?
    Each level of the tree is equivalent to multiplying the current value by 10 and adding node value. So when we go up the tree we should remove current value and divide by 10, or just drop the last digit. As a integer division by 10 is exactly doing this that's what I'm doing here.

    I hope this is clear, sorry if I'm struggling a bit to explain it in english


  • 0
    L

    Thanks Nergal. I used a similar method as you did, but did not take "add a right sub-tree once" into consideration. Thanks for your explanation, and I will modify my code correspondingly.


  • 0
    P

    This is a very nice solution. I spent so much time on iterative pre-order but couldn't make it work. Seems for this problem you have to use some post-order like iterative traversal.


Log in to reply
 

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