BinaryTreeLevelTraversal (要求用List<List<Integer>> 返回结果)

public static void  BFS(BTreeNode root,int level,ArrayList<ArrayList<Integer>> res){
           if (root == null) 
               return;         
           if (level >= res.size()) 
          res.add(new ArrayList<Integer>());         
           res.get(level).add((int)root.val);
  BFS(root.left,level+1,res);
  BFS(root.right,level+1,res);
  }
  
  public static ArrayList<ArrayList <Integer>> levelTravel1(BTreeNode root){
  ArrayList<ArrayList <Integer>> res=new ArrayList<ArrayList <Integer>>();
  BFS(root,0,res);
  return res;
  }
  
  
  public static ArrayList<ArrayList <Integer>> levelTravel2(BTreeNode root){
 
   ArrayList<ArrayList<Integer>> res = new ArrayList<>();
       if (root == null) 
            return res;   
       Queue<BTreeNode> queue = new LinkedList<BTreeNode>();
       queue.offer(root);
       while (!queue.isEmpty()) {
           ArrayList<Integer> level = new ArrayList<Integer>();
           int q_size = queue.size();
           for (int i = 0; i < q_size; i++) {
            BTreeNode curNode = queue.poll();    
               level.add(curNode.val);
               if (curNode.left != null) 
                   queue.offer(curNode.left);                
               if (curNode.right != null) 
                   queue.offer(curNode.right);                
           }
           res.add(level);
       }
       return res;
  }
  
  public static void main(String[] args) {
BTreeNode root = new BTreeNode(1);
   root.left = new BTreeNode(2);
        root.right = new BTreeNode(3);
        root.right.left = new BTreeNode(4);
        root.right.right = new BTreeNode(5);
        root.right.left.left=new BTreeNode(6);
        root.right.left.right=new BTreeNode(7);
        root.right.right.left = new BTreeNode(;
        root.right.right.right = new BTreeNode(9);
        ArrayList<ArrayList <Integer>> res=levelTravel2(root);
        levelTravel2(root);
        for(ArrayList<Integer> i: res)      
        System.out.println(i);     
        
        
}