二叉树的层序遍历 (opens new window)

• 难度：Medium
• 标签：DFS BFS 递归

刷题思路

• [x] 模板递归法(DFS)
• [x] 模板状态迭代法(DFS)
• [x] 模板递归法(BFS)
• [x] 模板状态迭代法(BFS)

方法 1 模板递归法(DFS)

• 思路: 每层加上level做标记。某level第一次出现创建数组并插入res, 同level数值放入同一数组。
• 复杂度:
  • 时间: O(n).等同二叉树节点个数，故为 O(n)
  • 空间: O(n).使用递归调用栈
• 结果:
  • 执行用时：84 ms, 在所有 JavaScript 提交中击败了77.97%的用户
  • 内存消耗：38.9 MB, 在所有 JavaScript 提交中击败了40.46%的用户

var levelOrder = function(root) {
    const res = []
    recursion (root, res, 0)
    return res
};

function recursion (root, res, level) {
    if (!root) return
    if (!res[level]) res[level] = []
    res[level].push(root.val)
    if (root.left) recursion(root.left, res, level+1)
    if (root.right) recursion(root.right, res, level+1)
}

方法 2 模板状态迭代法(DFS)

• 思路: 给节点加上level开始迭代.
• 复杂度:
  • 时间: O(n).
  • 空间: O(n).
• 结果:
  • 执行用时：76 ms, 在所有 JavaScript 提交中击败了94.05%的用户
  • 内存消耗：38.9 MB, 在所有 JavaScript 提交中击败了36.64%的用户

var levelOrder = function(root) {
    if (!root) return []
    root.level = 0
    const stack = [root]
    const res = []
    while (stack.length > 0) {
        const node = stack.pop()
        if (!res[node.level]) res[node.level] = []
        res[node.level].push(node.val)
        if (node.right) {
            node.right.level = node.level + 1
            stack.push(node.right)
        }
        if (node.left) {
            node.left.level = node.level + 1
            stack.push(node.left)
        }
    }
    return res
};

方法 3 模板递归法(BFS)

• 复杂度：
  • 时间: O(n).
  • 空间: O(n)
• 结果:
  • 执行用时：100 ms, 在所有 JavaScript 提交中击败了22.44%的用户
  • 内存消耗：39.4 MB, 在所有 JavaScript 提交中击败了8.76%的用户

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

function recursion (queue, res, level) {
    if (!queue || queue.length===0) return
    if (!res[level]) res[level] = []
    for (let i=0, len=queue.length; i<len; i++) {
        const node = queue.shift()
        res[level].push(node.val)
        if (node.left) queue.push(node.left)
        if (node.right) queue.push(node.right)
    }
    recursion(queue, res, level+1)
}

方法 4 模板状态迭代法(BFS)

• 思路: 提前将root塞进队列，以队列非空为条件开始循环. 以queue长度为次数循环，将当前值加入结果，将其左右子节点加入队列.
• 复杂度：
  • 时间: O(n).满二叉树下while循环logn次，for循环次数分别为1, 2, 4..., 综合时间复杂度为O(n)
  • 空间: O(n).满二叉树情况下为约为O(n/2)，即最底层长度
• 结果：
  • 执行用时：92 ms, 在所有 JavaScript 提交中击败了51.75%的用户
  • 内存消耗：39.2 MB, 在所有 JavaScript 提交中击败了14.55%的用户

var levelOrder = function(root) {
    if (!root) return []
    let level = 0
    const queue = [root]
    const res = []
    while (queue.length > 0) {
        if (!res[level]) res[level] = []
        for (let i=0, len=queue.length; i<len; i++) {
            const node = queue.shift()
            res[level].push(node.val)
            if (node.left) queue.push(node.left)
            if (node.right) queue.push(node.right)
        }
        level++
    }
    return res
};

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~