C# - single stack with forward flag


  • 1

    I see many solutions using a queue, but to me the stack is more appropriate as it naturally reverses the order. The only catch is that you need to not just reverse the traversal you need to know when to push left before right and vise versa. I use a flag to denote which direction we're traversing, other than that no reversal or insert is needed.

    You could go one step further and omit the flag and just use the size of lists being odd or even, but I like the flag, more readable.

        public IList<IList<int>> ZigzagLevelOrder(TreeNode root) 
        {
            IList<IList<int>> lists = new List<IList<int>>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            
            if (root != null) stack.Push(root);
            bool forward = true;
            
            while (stack.Count > 0)
            {
                lists.Add(new List<int>());
                Stack<TreeNode> nextStack = new Stack<TreeNode>();
                
                while (stack.Count > 0)
                {
                    TreeNode n = stack.Pop();
                    lists[lists.Count - 1].Add(n.val);
                    
                    if (forward)
                    {
                        if (n.left != null) nextStack.Push(n.left);
                        if (n.right != null) nextStack.Push(n.right);
                    }
                    else
                    {
                        if (n.right != null) nextStack.Push(n.right);
                        if (n.left != null) nextStack.Push(n.left);
                    }
                }
                
                forward = !forward;
                stack = nextStack;
            }
            
            return lists;
        }
    

Log in to reply
 

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