LeetCode: Binary Tree Zigzag Level Order Traversal C# https://leetcode.com/explore/interview/card/top-interview-questions-medium/108/trees-and-graphs/787/


  Given a binary tree, return the zigzag level order traversal of its
  nodes' values. (ie, from left to right, then right to left for the
  next level and alternate between).
  
  For example:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

  
  return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]



/// &lt;summary&gt;
/// https://leetcode.com/explore/interview/card/top-interview-questions-medium/108/trees-and-graphs/787/
/// &lt;/summary&gt;

[TestClass]
public class ZigzagLevelOrderTest
{
    [TestMethod]
    public void TestZigZag()
    {
        /*     3
              / \
             9  20
                /  \
               15   7
          */
        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&lt;IList&lt;int&gt;&gt; res = ZigzagLevelOrderClass.ZigzagLevelOrder(root);
        CollectionAssert.AreEqual(new List&lt;int&gt; { 3 }, res[0].ToList());
        CollectionAssert.AreEqual(new List&lt;int&gt; { 20, 9 }, res[1].ToList());
        CollectionAssert.AreEqual(new List&lt;int&gt; { 15, 7 }, res[2].ToList());
    }

    [TestMethod]
    public void FailedTest()
    {
        /*     1
              / \
             2   3
            /     \
            4      5
             */

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
        IList&lt;IList&lt;int&gt;&gt; res = ZigzagLevelOrderClass.ZigzagLevelOrder(root);
        CollectionAssert.AreEqual(new List&lt;int&gt; { 1 }, res[0].ToList());
        CollectionAssert.AreEqual(new List&lt;int&gt; { 3, 2 }, res[1].ToList());
        CollectionAssert.AreEqual(new List&lt;int&gt; { 4, 5 }, res[2].ToList());
    }

}

public class ZigzagLevelOrderClass
{
    public static IList&lt;IList&lt;int&gt;&gt; ZigzagLevelOrder(TreeNode root)
    {
        List&lt;IList&lt;int&gt;&gt; result = new List&lt;IList&lt;int&gt;&gt;();
        if (root == null)
        {
            return result;
        }
        Stack&lt;TreeNode&gt; currentLeveL = new Stack&lt;TreeNode&gt;();
        Stack&lt;TreeNode&gt; nextLevel = new Stack&lt;TreeNode&gt;();
        currentLeveL.Push(root);
        while (currentLeveL.Count &gt; 0 || nextLevel.Count &gt; 0)
        {
            var nodes = new List&lt;int&gt;();
            while (currentLeveL.Count &gt; 0)
            {
                var curr = currentLeveL.Pop();
                if (curr.left != null)
                {
                    nextLevel.Push(curr.left);
                }

                if (curr.right != null)
                {
                    nextLevel.Push(curr.right);
                }
                nodes.Add(curr.val);
            }

            if (nodes.Count &gt; 0)
            {
                result.Add(nodes);
            }
            nodes = new List&lt;int&gt;();
            while (nextLevel.Count &gt; 0)
            {
                var curr = nextLevel.Pop();
                if (curr.right != null)
                {
                    currentLeveL.Push(curr.right);
                }
                if (curr.left != null)
                {
                    currentLeveL.Push(curr.left);
                }
                nodes.Add(curr.val);
            }

            if (nodes.Count &gt; 0)
            {
                result.Add(nodes);
            }
        }

        return result;
    }
}


Please review for performance. this is the second time I solved this question. 
I think I did a better job now.
Your implementation is close, but it can be a bit shorter. You correctly use two stacks, but you duplicate the code alternating between using the two. That's a bit of a waste of space. Instead, at the end of the first while loop, you can just assign nextLevel to currentLevel, create a new stack to nextLevel, and repeat:

    while (currentLeveL.Count &gt; 0 || nextLevel.Count &gt; 0)
    {
        var nodes = new List&lt;int&gt;();
        while (currentLeveL.Count &gt; 0)
        {
            var curr = currentLeveL.Pop();
            if (curr.left != null)
            {
                nextLevel.Push(curr.left);
            }

            if (curr.right != null)
            {
                nextLevel.Push(curr.right);
            }
            nodes.Add(curr.val);
        }

        if (nodes.Count &gt; 0)
        {
            result.Add(nodes);
        }
        currentLevel = nextLevel;
        nextLevel = new Stack&lt;TreeNode&gt;();
    }


The while condition can also be made easier, nextLevel is known to be empty when it is evaluated:

while (currentLeveL.Count &gt; 0)




Since you're looping over the stack, only removing each item, not adding items back or anything, you can just replace the while for a foreach:

public static IList&lt;IList&lt;int&gt;&gt; ZigzagLevelOrder(TreeNode root)
{
    List&lt;IList&lt;int&gt;&gt; result = new List&lt;IList&lt;int&gt;&gt;();
    if (root == null)
    {
        return result;
    }
    Stack&lt;TreeNode&gt; currentLeveL = new Stack&lt;TreeNode&gt;();
    Stack&lt;TreeNode&gt; nextLevel = new Stack&lt;TreeNode&gt;();
    currentLeveL.Push(root);
    while (currentLeveL.Count &gt; 0)
    {
        var nodes = new List&lt;int&gt;();
        foreach(var curr in currentLeveL)
        { 
            if (curr.left != null)
            {
                nextLevel.Push(curr.left);
            }

            if (curr.right != null)
            {
                nextLevel.Push(curr.right);
            }
            nodes.Add(curr.val);
        }

        if (nodes.Count &gt; 0)
        {
            result.Add(nodes);
        }
        currentLeveL = nextLevel;
        nextLevel = new Stack&lt;TreeNode&gt;();
    }

    return result;
}