# NC15.求二叉树的层序遍历

# 描述

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）

例如：给定的二叉树是 {3,9,20,#,#,15,7},

该二叉树层序遍历的结果是:

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

1
2
3
4
5

# 思路

二叉树层序遍历的解题思路，不同于前、中后序的遍历思路，是需要使用迭代实现的，并且需要借助队列这种数据结构。

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
  * 
  * @param root TreeNode类 
  * @return int整型二维数组
  */
function levelOrder( root ) {
  // 首先做判空处理
  if(root === null) {
    return [];
  }
  let res = [];
  let queue = [];
  // 将根节点放进队列中
  queue.push(root);
  // 循环的条件就是队列中还有元素没有遍历完
  while(queue.length !== 0) {
    // 遍历一层需要创建一个数组存放当前层的元素
    let subarr = [];
    // 这个部分是必须将每一层的元素数量作为变量保存起来的
    // 因为在for循环内部，对于这个queue做了操作，如果不保存的话结果就会出现差异
    let levelnum = queue.length;
    for (let i = 0; i < levelnum; i++) {
      // 取出队列头部节点
      let node = queue.shift()
      // 将头部节点的值放入每层的数组中
      subarr.push(node.val)

      // 因为是从左向右遍历，所以入队的时候 先放左边 再放右边
      if (node.left !== null) {
        queue.push(node.left)
      }
      if (node.right !== null) {
        queue.push(node.right)
      }
    } 
    // 循环完毕一层之后将当前层的所有元素放进结果中
    res.push(subarr)
  }
  return res
}
module.exports = {
  levelOrder : levelOrder
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

注意：

取出队列头部节点的操作是放在for循环内部的，因为需要不断取值
记录每一层的数量使用的是一个变量存储在for循环的外部，因为for循环内对queue做了修改操作。