2.10 Binary Tree Zigzag Level Order Traversal

Description

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] ]

Method

method one: two stack

method two dfs

Time and Space Complexity

o(n) o(n)

Code

public class Solution {

 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
       List<List<Integer>> ans = new ArrayList<List<Integer>>();
       if (root == 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> list = new ArrayList<Integer>();
              if (s1.isEmpty()){
                  while (!s2.isEmpty()){
                        TreeNode node = s2.pop();
                         list.add(node.val);
                         if (node.right != null){
                             s1.push(node.right);
                         } 
                         if (node.left != null){
                             s1.push(node.left);
                         }
                  }
              } else {
                  while (!s1.isEmpty()){
                         TreeNode node = s1.pop();
                         list.add(node.val);
                         if (node.left != null){
                             s2.push(node.left);
                         }
                         if (node.right != null){
                             s2.push(node.right);
                         }
                  }
              }
              ans.add(list);
       }
       return ans;
}

}

method two: