Binary Tree Level Order Traversal

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]
]

Solution 1: do BFS, using two queues. One store the trees, and the other store the levels.

Java语言: BinaryTreeLevelOrderTraversal

01 public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {

02   ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();

03   ArrayList<TreeNode> trees=new ArrayList<TreeNode>();

04   ArrayList<Integer> depth=new ArrayList<Integer>();

05   ArrayList<Integer> firstLevel=new ArrayList<Integer>();

06 

07   if(root==null)

08     return results;          

09   trees.add(root);

10   depth.add(1);

11   firstLevel.add(root.val);

12   results.add(firstLevel);

13   while(!trees.isEmpty())

14   {

15     TreeNode top=trees.remove(0);

16     int curr_val=depth.remove(0);

17     if(top.left!=null)

18     {

19       trees.add(top.left);

20       depth.add(curr_val+1);

21     }

22     if(top.right!=null)

23     {

24       trees.add(top.right);

25       depth.add(curr_val+1);

26     }

27     int size=depth.size();

28     if(size>0 && depth.get(0)==depth.get(size-1) && curr_val==depth.get(0)-1)

29     {

30       ArrayList<Integer> curr_level=new ArrayList<Integer>();

31       for(int i=0;i<trees.size();i++)

32       {

33         curr_level.add(trees.get(i).val);

34       }

35       results.add(curr_level);

36     }

37   }

38   return results;

39 }

Solution 2: still using BFS and two queues. But both queue store the tree nodes, the current level and the next level. One the current level is empty but next level is not, output the result.

Java语言: BinaryTreeLevelOrder

01 public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {

02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>> ();

03     if(root==null)

04         return results;

05     LinkedList<TreeNode> thisLevel = new LinkedList<TreeNode>();

06     LinkedList<TreeNode> nextLevel = new LinkedList<TreeNode>();

07     thisLevel.add(root);

08     ArrayList<Integer> firstLine=new ArrayList<Integer>();

09     firstLine.add(root.val);

10     results.add(firstLine);

11     while(thisLevel.size()!=0)

12     {

13         TreeNode node = thisLevel.peek();

14         if(node.left!=null)

15         {

16             nextLevel.add(node.left);

17         }

18         if(node.right!=null)

19         {

20             nextLevel.add(node.right);

21         }

22         thisLevel.remove();

23         if(thisLevel.size()==0 && nextLevel.size()!=0)

24         {

25             ArrayList<Integer> level=new ArrayList<Integer>();

26             for(TreeNode n: nextLevel)

27             {

28                 level.add(n.val);

29             }

30             results.add(level);

31             thisLevel = nextLevel;

32             nextLevel = new LinkedList<TreeNode>();

33         }

34     }      

35     return results;

36 }

Solution 3: as BFS maintains two queues and is complex. A DFS method looks easier and concise. We just do a DFS, always remember the level of the current node, and assign the node to the correct level in the result list, then we are done!

Java语言: BinaryTreeLevelOrderDFS

01 public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
03     if(root==null)
04         return results;
05     //Start DFS from the root, level=0    
06     levelOrderDFS(results,root,0);
07     return results;
08 }
09 public void levelOrderDFS(ArrayList<ArrayList<Integer>> results, TreeNode node, int level)
10 {
11     //reach a new level, and created this level, add the node
12     if(results.size()-1<level)
13     {
14         ArrayList<Integer> newLevel=new ArrayList<Integer>();
15         newLevel.add(node.val);
16         results.add(newLevel);
17     }
18     //append the node to the existing level it correspond to
19     else
20     {
21         ArrayList<Integer> existLevel=results.get(level);
22         existLevel.add(node.val);
23         results.set(level,existLevel);
24     }
25     //DFS recursion on left and right respectively
26     if(node.left!=null)
27     {
28         levelOrderDFS(results,node.left,level+1);
29     }
30     if(node.right!=null)
31     {
32         levelOrderDFS(results,node.right,level+1);
33     }
34 }