Binary Tree Level Order Traversal

bfs
 1 /**
 2  * Definition for binary tree
 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 ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
12         // IMPORTANT: Please reset any member data you declared, as
13         // the same Solution instance will be reused for each test case.
14         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
15         if(root == null)
16             return result;
17         ArrayList<TreeNode> parents = new ArrayList<TreeNode>();
18         parents.add(root);
19         ArrayList<Integer> tmp = new ArrayList<Integer>();
20         tmp.add(root.val);
21         result.add(tmp);
22         travel(result, parents);
23         return result;
24     }
25     
26     private void travel(ArrayList<ArrayList<Integer>> result, ArrayList<TreeNode> parents)
27     {
28         if(parents.size() == 0)
29             return;
30         ArrayList<TreeNode> nodes = new ArrayList<TreeNode>();
31         for(TreeNode i: parents){
32             if(i.left != null)
33                 nodes.add(i.left);
34             if(i.right != null)
35                 nodes.add(i.right);
36         }
37         parents.clear();
38         parents.addAll(nodes);
39         if(nodes.size() > 0)
40         {
41             ArrayList<Integer> tmp = new ArrayList<Integer>();
42             for(TreeNode i: nodes){
43                 tmp.add(i.val);
44             }
45             result.add(tmp);
46         }
47         travel(result, parents);
48     }
49 }