C# - iterative - track seen with second stack


  • 0

    Here is a version where I track if the node has been popped yet using a flag stack, on the second pop we "visit" the node. More concise would be to have a data class for the node and the flag, but here I just use 2 stacks.

        public IList<int> PostorderTraversal(TreeNode root) 
        {
            IList<int> list = new List<int>();
            TreeNode node = root;
            Stack<TreeNode> nodeStack = new Stack<TreeNode>();
            Stack<bool> seenStack = new Stack<bool>();
            
            while (node != null || nodeStack.Count > 0)
            {
                if (node != null)
                {
                    nodeStack.Push(node);
                    seenStack.Push(false); // first time - no
                    node = node.left;
                }
                else
                {
                    node = nodeStack.Pop();
                    bool seen = seenStack.Pop();
                    
                    if (seen) 
                    {
                        list.Add(node.val);
                        node = null;
                    }
                    else
                    {
                        nodeStack.Push(node);
                        seenStack.Push(true); // second time - yes
                        node = node.right;
                    }
                }
            }
            return list;
        }
    

    Also here is the much simpler version using pre-order traversal and reversing the result upon return.

        public IList<int> PostorderTraversal(TreeNode root) 
        {
            IList<int> list = new List<int>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            if (root != null) stack.Push(root);
            
            while (stack.Count > 0)
            {
                TreeNode node = stack.Pop();
                list.Add(node.val);
                if (node.left != null) stack.Push(node.left);
                if (node.right != null) stack.Push(node.right);
            }
            return list.Reverse().ToList();
        }
    

Log in to reply
 

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