Wednesday, October 17, 2012

Binary Tree Zigzag Level Order Traversal

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]
] 
 
Java Code:
 
  public static ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root)
    {
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>> ();
        ArrayList<TreeNode> tmpQ = new ArrayList<TreeNode> ();
        
        int i = 0;
        
        if(root != null)
            tmpQ.add(root);
    
        while ( !tmpQ.isEmpty() )
        {
            ArrayList<Integer> tmpresult = new ArrayList<Integer> ();
            int length = tmpQ.size();
            int count = 0;
            
            for (int z = 0; z < length; z++)
                tmpresult.add(tmpQ.get(z).val);
            
            while( count < length)
            {
                TreeNode tmp = tmpQ.get(length - 1 - count);
                tmpQ.remove(length-1-count);
                
                count++;
                
               if (i%2 == 0)
                {
                   if(tmp.right != null)
                       tmpQ.add(tmp.right);
                   if(tmp.left != null)
                       tmpQ.add(tmp.left);
                }
               else 
               {
                   if(tmp.left != null)
                       tmpQ.add(tmp.left);
                   if(tmp.right != null)
                       tmpQ.add(tmp.right);   
               }
             
            }
            
            results.add(tmpresult);
            i++;
        
        }
    
        return results;
    
    }

No comments:

Post a Comment