My C# submission, easy-to-understand, >97% runtime distribution


  • 0
    E

    Basically this algorithm uses a Stack in combination with an alternating directional flag to recursively traverse the binary tree in a zig-zag pattern.

    This is my first submission to a discussion so let me know if I can improve anything! Code can probably be cleaned up but the runtime is pretty efficient so I'll just post what I have.

    Here's the code:

    public class Solution
    {
        public IList<IList<int>> ZigzagLevelOrder(TreeNode root)
        {
            IList<IList<int>> order = new List<IList<int>>();
    
            if (root == null)
            {
                return order;
            }
    
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.Push(root);
            traverse(order, stack, false);
    
            return order;
        }
    
        private void traverse(IList<IList<int>> order, Stack<TreeNode> stack, bool flag)
        {
            IList<int> currentRow = new List<int>();
            Stack<TreeNode> nextRow = new Stack<TreeNode>();
            flag = (flag) ? false : true; // flip traversal direction
    
            while (stack.Count > 0)
            {
                TreeNode currentNode = stack.Pop();
                currentRow.Add(currentNode.val);
                if (flag) // traverse right --> left (add to stack in reverse)
                { 
                    if (currentNode.left != null)
                    {
                        nextRow.Push(currentNode.left);
                    }
                    if (currentNode.right != null)
                    {
                        nextRow.Push(currentNode.right);
                    }
                }
                else // traverse left --> right (add to stack in reverse)
                { 
                    if (currentNode.right != null)
                    {
                        nextRow.Push(currentNode.right);
                    }
                    if (currentNode.left != null)
                    {
                        nextRow.Push(currentNode.left);
                    }
                }
            }
    
            order.Add(currentRow);
    
            if (nextRow.Count > 0)
            {
                traverse(order, nextRow, flag);
            }
    
            return;
        }
    }
    

Log in to reply
 

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