102. 二叉树的层序遍历

;(function () {
  /**
   * 102. 二叉树的层序遍历
   * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
   *
   * 输入：root = [3,9,20,null,null,15,7]
   * 输出：[[3],[9,20],[15,7]]
   *
   * 输入：root = [1]
   * 输出：[[1]]
   *
   * 输入：root = []
   * 输出：[]
   *
   * 【DFS 与 BFS】
   * https://leetcode.cn/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/
   *
   */
  class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
      this.val = val === undefined ? 0 : val
      this.left = left === undefined ? null : left
      this.right = right === undefined ? null : right
    }
  }

  function levelOrder(root: TreeNode | null): number[][] {
    // 方法一：递归（竟然被我蒙对了）
    let res: number[][] = []
    let index = 0
    // 这里还可以加一些临界条件判断，提高代码性能，比如： if(!root) return res 等
    function preorder(root: TreeNode | null, index: number) {
      if (!root) return
      !res[index] ? (res[index] = []) : null
      res[index].push(root.val)
      let k = ++index
      preorder(root.left, k)
      preorder(root.right, k)
    }
    preorder(root, index)
    return res
  }
})()