JAVA Double Stack Solution


  • 20
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
       TreeNode c=root;
       List<List<Integer>> ans =new ArrayList<List<Integer>>();
       if(c==null) return ans;
       Stack<TreeNode> s1=new Stack<TreeNode>();
       Stack<TreeNode> s2=new Stack<TreeNode>();
       s1.push(root);
       while(!s1.isEmpty()||!s2.isEmpty())
       {
           List<Integer> tmp=new ArrayList<Integer>();
            while(!s1.isEmpty())
            {
                c=s1.pop();
                tmp.add(c.val);
                if(c.left!=null) s2.push(c.left);
                if(c.right!=null) s2.push(c.right);
            }
            ans.add(tmp);
            tmp=new ArrayList<Integer>();
            while(!s2.isEmpty())
            {
                c=s2.pop();
                tmp.add(c.val);
                if(c.right!=null)s1.push(c.right);
                if(c.left!=null)s1.push(c.left);
            }
            if(!tmp.isEmpty()) ans.add(tmp);
       }
       return ans;
    }

  • 0
    E

    while(!s1.isEmpty()||!s2.isEmpty())

    is not necessary, because when s1 is empty s2 must be empty, so just judge

    while(!s1.isEmpty()) is enough.


  • 0

    Thank you, I didn't notice that.


  • 0
    K

    Hi,

    I solved it using LinkedList of list of integers, the stack solution didn't strike to me naturally.
    Could you explain a bit of your thinking logic behind the process?

    Thanks.


  • 1

    Because of the FILO property of stack, when you fill up a stack with one level of node, the output order of stack is reversed order of the input order. So you do it level by level, you will get zigzag order. Hope it helps.


  • 0
    E

    It's difficult to find the same solution like me that using two stack,there's many solution using queue.

    public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root==null){
            return result;
        }
        Stack<TreeNode> odd = new Stack<TreeNode>();
        Stack<TreeNode> even = new Stack<TreeNode>();
        even.push(root);
        while(!odd.isEmpty() || !even.isEmpty()){
              ArrayList<Integer> row = new ArrayList<Integer>();
              if(!even.isEmpty()){
                  while(!even.isEmpty()){
                      TreeNode cur = even.pop();
                      row.add(cur.val);
                      if(cur.left!=null){
                          odd.push(cur.left);
                      }
                      if(cur.right!=null){
                          odd.push(cur.right);
                      }
                  }
              }else{
                  while(!odd.isEmpty()){
                      TreeNode cur = odd.pop();
                      row.add(cur.val);
                      if(cur.right!=null){
                          even.push(cur.right);
                      }
                      if(cur.left!=null){
                          even.push(cur.left);
                      }
                  }
              }
              result.add(row);
        }
        return result;
    }
    

    }


  • 0
    A

    My python solution with two stacks

        def zigzagLevelOrder(self, root):
            if(root is None): return []
            stack,backupstack=[root],[]
            rt=[[]]
            depth=0
            while(stack or backupstack):
                if(stack):
                    node=stack.pop()
                    rt[depth].append(node.val)
                    if(depth%2==0):
                        if(node.left):backupstack.append(node.left)
                        if(node.right):backupstack.append(node.right)
                    else:
                        if(node.right):backupstack.append(node.right)
                        if(node.left):backupstack.append(node.left)
                else:
                    #switch
                    backupstack,stack=stack,backupstack
                    rt.append([])
                    depth+=1
            return rt
    

  • 0

    one of your stacks can be temp created during iteration and not kept outside your while loop. Otherwise I have the same here, C#

        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;
        }
    

  • 0
    A

    Here is my Java Double Stack solution:

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<Integer> tmpList;
            List<List<Integer>> result = new ArrayList<>();
            if(root == null) return result;
            
            Stack<TreeNode> st = new Stack<TreeNode>();
            Stack<TreeNode> st2 = new Stack<TreeNode>();
            st.push(root);
            while(!st.isEmpty() || !st2.isEmpty()) {
                boolean isStEmpty = st.isEmpty();
                Stack<TreeNode> currStack = isStEmpty ? st2 : st;
                Stack<TreeNode> otherStack = isStEmpty ? st : st2;
                tmpList = new ArrayList<>();
                while(!currStack.isEmpty()) {
                    TreeNode currNode = currStack.pop();
                    tmpList.add(currNode.val);
                    if(!isStEmpty) {
                        if(currNode.left != null) otherStack.push(currNode.left);
                        if(currNode.right != null) otherStack.push(currNode.right);
                    } else {
                        if(currNode.right != null) otherStack.push(currNode.right);
                        if(currNode.left != null) otherStack.push(currNode.left);
                    }
                }
                result.add(tmpList);
            }
            return result;
        }
    

Log in to reply
 

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