C++ easy to understand code with explanation. similar approach as recursion


  • 0
    W

    use a stack since can't use the stack frame that's used for recursion. Pop the current node when both children are visited, just like in recursion you take care of the current node only after both left and right child are visited. Use set to keep track whether children are visited.

    // just here for comparison with iterative solution below
    void postorderRecursive(TreeNode* node, vector<int>& result)
    {
        if (!node) return;
        
        postorderRecursive(node->left, result);
        postorderRecursive(node->right, result);
        result.push_back(node->val);
    }
    
    vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int> result;
        if (!root) return result;
        
        stack<TreeNode*> myStack;
        unordered_set<TreeNode*> visitedNodes;
        myStack.push(root);
        
        while (!myStack.empty())
        {
            bool hasUnvisitedChildren = false;
            auto node = myStack.top();  // don't pop now. pop after children are visited just like in recursion
            if (node->right && visitedNodes.count(node->right) == 0)  // this prevents reinserting same children
            {
                myStack.push(node->right);
                hasUnvisitedChildren = true;
            }
            if (node->left && visitedNodes.count(node->left) == 0)
            {
                myStack.push(node->left);
                hasUnvisitedChildren = true;
            }
            
            if (!hasUnvisitedChildren)
            {
                myStack.pop();
                result.push_back(node->val);
                visitedNodes.insert(node);
            }
        }
    
        return result;
    }

  • 0
    J

    Hi, we got almost the same solution!

    class Solution{
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> poTraverse;
            if (!root) return poTraverse;
            stack<TreeNode*> nodes;
            unordered_set<TreeNode*> visited;
            TreeNode* cur = root;
            nodes.push(cur);
            while(!nodes.empty())
            {
                if (cur->left && (visited.find(cur->left) == visited.end()))
                {
                    nodes.push(cur);
                    cur = cur->left;
                }
                else if (cur->right && (visited.find(cur->right) == visited.end()))
                {
                    nodes.push(cur);
                    cur = cur->right;
                }
                else
                {
                    poTraverse.push_back(cur->val);
                    visited.insert(cur);
                    cur = nodes.top();
                    nodes.pop();
                }
            }
            return poTraverse;
        }
    };

Log in to reply
 

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