LevelOrderTraversal

//Given a binary tree, return the level order traversal of its nodes' values. (ie, from 


left to right, level by level).
//
//For example:
//Given binary tree {3,9,20,#,#,15,7},
//    3
//   / \
//  9  20
//    /  \
//   15   7
//return its level order traversal as:
//[
//  [3],
//  [9,20],
//  [15,7]
//]








public class LevelOrderTraversal {


public static void main(String[] args) {
// TODO 自动生成的方法存根
TreeNode root=new TreeNode(1);
TreeNode root1=new TreeNode(2);
TreeNode root2=new TreeNode(3);
TreeNode root3=new TreeNode(4);
TreeNode root4=new TreeNode(5);
root.left=root1;
root1.left=root2;
root2.left=root3;
root3.left=root4;
root4.left=root4;
ArrayList> mq=new ArrayList>();
mq=(ArrayList>) levelOrder(root);

System.out.print(mq);
}
public static  List> levelOrder(TreeNode root) {
ArrayList> m=new ArrayList>();
ArrayList> f=new ArrayList>();
   if(root==null)
    return m;
   int i=0;
   TreeNode qNode1=root;
   Queue n=new LinkedList();
Queue queues=new LinkedList();
TreeNode tempNode=root;
TreeNode newNode;
queues.offer(root);
while(!queues.isEmpty()){
tempNode=queues.poll();
n.offer(tempNode);
if(tempNode.left!=null){
queues.offer(tempNode.left);
}
if(tempNode.right!=null){
queues.offer(tempNode.right);
}
}
int w=0;
int k=0;
int z=0;
List list=new ArrayList();
List list1=new ArrayList();
List list2=new ArrayList();
List list3=new ArrayList();
list.add(root);
list1.add(root.val);
f.add(list);
m.add(list1);
int s=n.size();
k++;
n.poll();
if(s==1){
   return m;
}
for (int j = 1; j
newNode=n.poll();
for(w=0;w if(newNode.equals(f.get(k-1).get(w).left)|| 


newNode.equals(f.get(k-1).get(w).right)){
list2.add(newNode);
list3.add(newNode.val);
break;
}

}
  if(w>=f.get(k-1).size()){
  
   f.add(list2);
m.add(list3);
k++;
list2=new ArrayList();
list3=new ArrayList();
list2.add(newNode);
list3.add(newNode.val);
  }
}

f.add(list2);
m.add(list3);

    return m;   
  }
}