Java 2 stacks solution with explanation


  • 0
    A

    Because the traversal is zigzag, that means the direction is different between two continues levels. So I create two stacks, one for odd and one for even.

    Odd stacks push the subtree of nodes from left to right.
    Even stacks push the subtree of nodes from right to left;

    Remember to check the list1 and list2 before adding them to the final list. Otherwise, there might be some empty list in the final list.

    
    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            
            List<List<Integer>> list = new LinkedList<List<Integer>>();
            Stack<TreeNode> stack1 = new Stack<TreeNode>();
            Stack<TreeNode> stack2 = new Stack<TreeNode>();
            
            if(root==null)
                return list;
                
            TreeNode head = root;
            stack1.push(head);
            
            while(!stack1.isEmpty()||!stack2.isEmpty()){
                
                //stack1
                List<Integer> list1 = new LinkedList<Integer>();
                while(!stack1.isEmpty()){
                    TreeNode temp = stack1.pop();
                    list1.add(temp.val);
                    if(temp.left!=null)
                        stack2.push(temp.left);
                    if(temp.right != null)
                        stack2.push(temp.right);
                }
                
                //stack2
                List<Integer> list2 = new LinkedList<Integer>();
                while(!stack2.isEmpty()){
                    TreeNode temp = stack2.pop();
                    list2.add(temp.val);
                    if(temp.right != null)
                        stack1.push(temp.right);
                    if(temp.left!= null)
                        stack1.push(temp.left);
                }
                
                //add list1 and list2 into final list
                if(!list1.isEmpty())
                    list.add(list1);
                if(!list2.isEmpty())
                    list.add(list2);
            }
            return list;
        }
    }
    

Log in to reply
 

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