102.二叉树的层序遍历

102.二叉树的层序遍历

遍历本身很简单,需要考虑的问题是怎么标示每一层,这里可以用迭代和递归两种思路

迭代
  1. 入队 root ,再入队一个null 表示第 0 层的结束
  2. 出队 root ,入队左右节点 , 如果出队的是null,说明一层结束,再入队一个 null
  3. 队列不为空,循环 2

⚠️ 需要注意的点: 队列最后一项如果不做处理将会一直是null,因此需要增加结束条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var levelOrder = function(root) {
var que = [root,null]
var res = []
var level = []
if (!root ) return []
while(que.length) {
var node = que.shift()
if (node) {
node.left && que.push(node.left)
node.right && que.push(node.right)
level.push(node.val)
} else {
res.push([...level])
level = []
if(que.length) {
que.push(null)
}
}
}
return res
};
递归

递归解法的重点是传递层数作为参数

1
2
3
4
5
6
7
8
9
10
11
12
var levelOrder = function(root) {
var res = []
if (!root) return []
var walk = function (node,index) {
if (!res[index]) res[index] = []
res[index].push(node.val)
node.left && walk(node.left,index + 1)
node.right && walk(node.right,index + 1)
}
walk(root,0)
return res
};

步骤如代码所示

  1. 为所在的层数开辟一个数组空间
  2. root 加入数组
  3. 如果存在左节点,或者右节点,继续到1,层数 + 1