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

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

刷题思路

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

方法 1 模板递归法(BFS)

• 复杂度：
  • 时间 O(n)
  • 空间 O(n)
• 结果：
  • 执行用时：104 ms, 在所有 JavaScript 提交中击败了82.14%的用户
  • 内存消耗：41.3 MB, 在所有 JavaScript 提交中击败了66.22%的用户

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

function recursion (nodes, res, level) {
    if (nodes.length === 0) return
    if (!res[level]) res[level] = []
    const childNodes = []
    nodes.forEach(node => {
        res[level].push(node.val)
        node.children.forEach(v => childNodes.push(v))
    })
    recursion(childNodes, res, level+1)
}

方法 2 模板迭代法(BFS)

• 复杂度：
  • 时间 O(n)
  • 空间 O(n)
• 结果：
  • 执行用时：112 ms, 在所有 JavaScript 提交中击败了58.54%的用户
  • 内存消耗：41.2 MB, 在所有 JavaScript 提交中击败了72.44%的用户

var levelOrder = function(root) {
    if (!root) return []
    const res = []
    const queue = [root]
    let level = 0
    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.children) node.children.forEach(item => queue.push(item))
        }
        level++
    }
    return res
};

方法 3 模板递归法(DFS)

• 复杂度：
  • 时间 O(n)
  • 空间 O(n)
• 结果：
  • 执行用时：148 ms, 在所有 JavaScript 提交中击败了6.94%的用户
  • 内存消耗：48.1 MB, 在所有 JavaScript 提交中击败了5.25%的用户

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

function recursion (node, res, level) {
    if (!node) return
    if (!res[level]) res[level] = []
    res[level].push(node.val)
    if (node.children) {
        node.children.forEach(item => recursion(item, res, level+1))
    }
}

方法 4 模板迭代法(DFS)

• 复杂度：
  • 时间 O(n)
  • 空间 O(n)
• 结果：
  • 执行用时：116 ms, 在所有 JavaScript 提交中击败了45.03%的用户
  • 内存消耗：41.3 MB, 在所有 JavaScript 提交中击败了68.77%的用户

var levelOrder = function(root) {
    if (!root) return []
    const res = []
    root.level = 0
    const stack = [root]
    while (stack.length > 0) {
        const node = stack.pop()
        if (!res[node.level]) res[node.level] = []
        res[node.level].push(node.val)
        if (node.children) {
            const len = node.children.length
            for (let i=len-1; i>=0; i--) { // 为了 DFS 所以需要反向遍历入栈
                node.children[i].level = node.level + 1
                stack.push(node.children[i])
            }
        }
    }
    return res
};

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