102. 二叉树的层序遍历

[Geekhyt]

原题链接

DFS 深度优先遍历

按照树的深度将每层对应的节点添加到对应层的数组中即可。

const levelOrder = function(root) {
    if (!root) return []
    const res = []
    dfs(root, 0, res)
    return res
};

const dfs = function(root, depth, res) {
    if (!root) return // 递归终止条件
    if (!res[depth]) res[depth] = []
    res[depth].push(root.val) // 存入每层的节点值
    dfs(root.left, depth + 1, res) // drill down
    dfs(root.right, depth + 1, res)
}

BFS 广度优先遍历

根据层次返回其对应的结果集合。

1.边界处理，初始化队列 queue 和存放结果的数组 res。
2.外层循环遍历层级结构，内层循环遍历每一层的子节点。
3.遍历时需要记录当前层的遍历次数 len 以及当前层的节点数组 arr。
4.取得 node 依次出队，并依次存入当前层的节点数组中。
5.若存在左右子节点，则依次入队，并更新 len。
6.遍历完后返回结果 res。

const levelOrder = function(root) {
    if (!root) return []
    const queue = [root]
    const res = []
    while (queue.length > 0) {
      const arr = []
      let len = queue.length
      while (len) {
        let node = queue.shift()
        arr.push(node.val)
        if (node.left) queue.push(node.left)
        if (node.right) queue.push(node.right)
        len--
      }
      res.push(arr)
    }
    return res
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)