C# iteration use two stack


  • 0
    C

    C# iteration use two stack. Loop each layer and push all nodes to another stack with opposite sequence

        public IList<IList<int>> ZigzagLevelOrder(TreeNode root)
        {
            List<IList<int>> result = new List<IList<int>>();
    
            if (root == null)
            {
                return result;
            }
    
            Stack<TreeNode> s1 = new Stack<TreeNode>();
            Stack<TreeNode> s2 = new Stack<TreeNode>();
    
            s1.Push(root);
    
            while (s1.Count != 0 || s2.Count != 0)
            {
                int n1 = s1.Count;
                int n2 = s2.Count;
    
                List<int> list = new List<int>();
    
                for (int i = 0; i < n1; i++)
                {
                    root = s1.Pop();
                    list.Add(root.val);
    
                    if (root.left != null)
                    {
                        s2.Push(root.left);
                    }
    
                    if (root.right != null)
                    {
                        s2.Push(root.right);
                    }
                }
    
                for (int i = 0; i < n2; i++)
                {
                    root = s2.Pop();
                    list.Add(root.val);
    
                    if (root.right != null)
                    {
                        s1.Push(root.right);
                    }
    
                    if (root.left != null)
                    {
                        s1.Push(root.left);
                    }
                }
    
                result.Add(list);
            }
    
            return result;
        }

Log in to reply
 

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