zhangdi

102.二叉树层序遍历 ​

题目 ​

LeetCode 中等

题目

给你二叉树的根节点 root ，返回其节点值的层序遍历（即逐层地，从左到右访问所有节点）。

例如：
给定的二叉树是[3,9,20,null,null,15,7],
该二叉树层序遍历的结果是 [[3], [9,20], [15,7]]

题解 ​

BFS 队列 O(n) O(n)

ts
function levelOrder(root: TreeNode | null): number[][] {
  const res = []
  if (root) {
    let queue: [TreeNode, number][] = [[root, 0]]
    while (queue.length) {
      console.log('queue ' + queue.map(i => `[${i[0].val} ${i[1]}]`))
      console.log(res.map(i => i.toString()))
      console.log('-----')

      const [node, i] = queue.shift()
      res[i] = res[i] || []
      res[i].push(node.val)
      if (node.left) queue.push([node.left, i + 1])
      if (node.right) queue.push([node.right, i + 1])
    }
  }
  return res
}

const tree = new Tree([3, 9, 20, null, null, 15, 7])
console.log('🌰', levelOrder(tree.root))