zhangdizhangdi

102. 二叉树层序遍历 🟨

题目

LeetCode 中等

题目

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

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

题解

广度优先 BFS 队列

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
js 
// 1. 定义二叉树节点
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function levelOrder(root) {
  const res = []
  if (root) {
    let queue = [[root, 0]]
    while (queue.length) {
      console.log(
        'queue ' + JSON.stringify(queue.map(([node, i]) => [node.val, i])),
      )
      console.log('res ' + JSON.stringify(res.map(i => i)))
      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
}

//       3
//      / \
//     9   20
//         / \
//        15  7
const treeA = new TreeNode(3)
treeA.left = new TreeNode(9)
treeA.right = new TreeNode(20, new TreeNode(15), new TreeNode(7))

console.log(JSON.stringify(levelOrder(treeA))) // [[3], [9, 20], [15, 7]]
执行结果 
queue [[3,0]]
res []
-----
queue [[9,1],[20,1]]
res [[3]]
-----
queue [[20,1]]
res [[3],[9]]
-----
queue [[15,2],[7,2]]
res [[3],[9,20]]
-----
queue [[7,2]]
res [[3],[9,20],[15]]
-----
[[3],[9,20],[15,7]]