Question

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,#,#,15,7},

3   / \  9  20    /  \   15   7

 

return its zigzag level order traversal as:

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

Solution

Traditional way is to use two queues to implement level order traversal. Here, we just add a flag to indicate whether it's from left to right or from right to left.

1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11     public List
     
      
       > zigzagLevelOrder(TreeNode root) {12         List
       
        
         > result = new ArrayList
         
          
           >();13 if (root == null)14 return result;15 // Set a flag to help judge traversal sequence16 // flag = 0, from left to right; flag = 1, from right to left17 int flag = 0;18 List
           
             current = new ArrayList
            
             ();19 List
             
               next;20 current.add(root);21 22 while (current.size() > 0) {23 List
              
                oneRecord = new ArrayList
               
                ();24 next = new ArrayList
                
                 ();25 for (TreeNode tmpNode : current) {26 if (tmpNode.left != null)27 next.add(tmpNode.left);28 if (tmpNode.right != null)29 next.add(tmpNode.right);30 if (flag == 0)31 oneRecord.add(tmpNode.val);32 else33 oneRecord.add(0, tmpNode.val);34 }35 result.add(oneRecord);36 current = next;37 flag = 1 - flag;38 }39 return result;40 }41 }