LeetCode-102.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,null,null,15,7],

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

重点是如何将每层隔开，使用广度优先遍历，时间复杂度为O(n):

 1  public List<List<Integer>> levelOrder(TreeNode root) {//树 BFS my
 2         Queue<TreeNode> queue = new LinkedList<>();
 3         List<List<Integer>> re = new ArrayList<>();
 4         if(null!=root){
 5             queue.add(root);
 6             queue.add(null);
 7         }
 8         while(!queue.isEmpty()&&null!=queue.peek()){//本方法使用null隔开每一层，也可以记录每一层的个数
 9             List<Integer> list = new ArrayList<>();
10             TreeNode cur = queue.poll();
11             while(null!=cur){
12                 list.add(cur.val);
13                 if(null!=cur.left){
14                     queue.add(cur.left);
15                 }
16                 if(null!=cur.right){
17                     queue.add(cur.right);
18                 }
19                 cur=queue.poll();
20             }
21             queue.add(null);
22             if(!list.isEmpty()){
23                 re.add(list);
24             }
25         }
26         return re;
27     }


也可以使用DFS完成

相关题
剑指offer 从上往下打印二叉树 https://www.cnblogs.com/zhacai/p/10692711.html