102.二叉树的层序遍历

发表于 | 分类于
Binary Tree Level Order Traversal

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