Leetcode 103 - Binary tree zigzag level order

Leetcode103_binaryTreeZigzagLevelOrder.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _103BTreeZigzagLevelOrderTraversal
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }

    class zigZagOrder
    {

        static void Main(string[] args)
        {
            TreeNode root = new TreeNode(3);
            root.left = new TreeNode(9);
            root.right = new TreeNode(20);
            root.right.left = new TreeNode(15);
            root.right.right = new TreeNode(7);

            IList<IList<int>> output = zigzagOutput(root);
        }

        /*
         * Leetcode 103 
         * Tree Zigzag Level Order output 
         * https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
         * 
         * pass online judge
         * Reference: 
         * 
         * http://rleetcode.blogspot.ca/2014/02/binary-tree-zigzag-level-order.html
         * Time Complexity is O(n)
            Take advantage of two stack
            one is used hold current level's node another is used to hold next level's hold,
            moreover there is flag used to mark the sequece (left to rigth or right to left)
            put the root first into current stack then pop it out, put left and right into next_level stack 
            (pay attention to sequence)
            once current stack is empty swap current and next level, level ++, 
            reverse sequence
         * 
         * Julia's comment: 
         * 1. Go through online judge
         * 2. Improve code readability, and improve the code - 
         * 3. Read more blogs about this problem and its solutions through leetcode blog, understand 
         *    better about various solution, and coding level, use best code for me to memorize. 
         * 4. Write down the thought process, extension discussion etc. 
 
         */
        public static IList<IList<int>> zigzagOutput(TreeNode root)
        {
            IList<IList<int>> result = new List<IList<int>>();
            if (root == null)
                return result;

            Stack<TreeNode> currLevel = new Stack<TreeNode>();
            Stack<TreeNode> nextLevel = new Stack<TreeNode>();

            currLevel.Push(root);
            bool normalOrder = true;                         

            IList<int> currLevelNodes = new List<int>();

            while (true)
            {
                // go through Queue - level by level, maintain order by normalOrder variable 
                 
                while (currLevel.Count != 0)
                {
                    TreeNode node = currLevel.Pop();
                    currLevelNodes.Add(node.val);

                    if (normalOrder)
                    {
                        if (node.left != null)
                            nextLevel.Push(node.left);
                        if (node.right != null)
                            nextLevel.Push(node.right);
                    }
                    else
                    {
                        if (node.right != null)
                            nextLevel.Push(node.right);
                        if (node.left != null)
                            nextLevel.Push(node.left);
                    }
                }

                if (currLevel.Count == 0)
                {
                    if (currLevelNodes != null && currLevelNodes.Count > 0)
                    {
                        result.Add(currLevelNodes);

                        currLevelNodes = new List<int>(); 
                    }

                    //swap(currLevel, nextLevel);   // bug - no swap, need to pas reference May 31, 2016
                    swap(ref currLevel, ref nextLevel);

                    normalOrder = !normalOrder;
                }

                if (currLevel == null || currLevel.Count == 0)
                    break;
            }

            return result;
        }

        private static void swap(ref Stack<TreeNode> current, ref Stack<TreeNode> next)
        {
            Stack<TreeNode> tmp = current;
            current = next;
            next = tmp;
        }
    }
}