zhangdizhangdi

429.N叉树的层序遍历

原题

LeetCode 中等

题目

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例：
输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

广度优先 BFS 队列 O(n) O(n)

ts
const tree: TreeNodeWithChildren = {
  val: 2,
  children: [
    { val: 6, children: [{ val: 1 }] },
    { val: 3, children: [{ val: 2 }, { val: 3 }, { val: 4 }] },
    { val: 5, children: [{ val: 7 }, { val: 8 }] },
  ],
}

function levelOrder(root: TreeNodeWithChildren | null): number[][] {
  if (!root) return []
  const res = []
  const queue = [root]
  while (queue.length) {
    const len = queue.length
    const level = []
    for (let i = 0; i < len; i++) {
      const node = queue.shift()
      level.push(node.val)
      if (node.children) {
        for (let n of node.children) {
          queue.push(n)
        }
      }

      console.log(queue.map(i => i.val))
    }
    res.push(level)
  }
  return res
}

console.log('🌰', levelOrder(tree))

每层节点和

ts
function everyLevelSum(root: TreeNodeWithChildren) {
  if (!root) return []
  const res = []
  const queue = [root]
  while (queue.length) {
    const len = queue.length
    const level = []
    for (let i = 0; i < len; i++) {
      const node = queue.shift()
      level.push(node.val)
      if (node.children) {
        for (let n of node.children) {
          queue.push(n)
        }
      }
    }
    res.push(level.length)
  }
  return res
}

console.log('🌰', everyLevelSum(tree))

指定层节点和

ts
function targetLevelSum(root: TreeNodeWithChildren, level: number) {
  if (!root) return 0
  const queue = [root]
  let curLevel = 1
  while (queue.length) {
    const len = queue.length
    const data = []
    for (let i = 0; i < len; i++) {
      const node = queue.shift()
      data.push(node.val)
      if (node.children) {
        for (let n of node.children) {
          queue.push(n)
        }
      }
    }
    if (level === curLevel) {
      return data.length
    }
    curLevel++
  }
  return 0
}

console.log('🌰', targetLevelSum(tree, 3))