Simple solution, single stack, no reversal.


  • 0
    T

    We can use a 'marker' node in the stack to indicate whether the node was already processed. If the node is already processed, we can include in the result. Else we mark it as 'processed' and push the right and left nodes into the stack.

      public IList<int> PostorderTraversal(TreeNode root)
                {
                    TreeNode markerNode = new TreeNode(-1);
                    Stack<TreeNode> s = new Stack<TreeNode>();
                    IList<int> result = new List<int>();
    
                    if (root != null)
                    {
                        s.Push(root);
                    }
    
                    while(s.Count != 0)
                    {
                        TreeNode curr = s.Pop();
                        if(s.Count == 0 || s.Peek() != markerNode)
                        {
                           // node is unprocessed
                            s.Push(markerNode);
                            s.Push(curr);
                            if(curr.right != null)
                            {
                                s.Push(curr.right);
                            }
                            if(curr.left != null)
                            {
                                s.Push(curr.left);
                            }
                        }
                        else
                        {
                           //node is aleady processed
                            s.Pop(); //remove marker
                            result.Add(curr.val);
                        }
                    }
                    return result;
                }
    

Log in to reply
 

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