102. 二叉树的层序遍历

迭代

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) {
    return []
  }

  const result = []
  const stack = [] // 当前层的栈
  let depth = 0;

  stack.push(root)

  // 遍历多少层
  while (stack.length) {
    // 添加最新一层的空数组
    // 也可以直接 result.push([])
    result[depth] = []

    const size = stack.length

    // 遍历当前层
    for (let i = 0; i < size; i += 1) {
      const currentRoot = stack.shift()

      // 用 shift 按照顺序取元素，然后添加到对应层的结果中
      result[depth].push(currentRoot.val)

      if (currentRoot.left) {
        stack.push(currentRoot.left)
      }

      if (currentRoot.right) {
        stack.push(currentRoot.right)
      }
    }

    // 增加深度
    // 也可以使用 result.length 来获取深度
    depth += 1
  }

  return result
}

递归

这样只是收集到的结果是正确的，遍历顺序还是深度遍历，如果遇到需要提前结束的场景就不支持了

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) {
    return []
  }

  const result = []

  // 定义递归函数
  function traverse(root: TreeNode, depth: number) {
    // 如果对应的深度还没有创建数组，先创建
    if (!result[depth]) {
      result[depth] = []
    }

    // 前中后序遍历递归的顺序都是正确的

    // 往对应的位置 push 当前的结果
    // result[depth].push(root.val)

    // 递归处理左结点
    if (root.left) {
      traverse(root.left, depth + 1)
    }

    // 递归处理右结点
    if (root.right) {
      traverse(root.right, depth + 1)
    }
  }

  traverse(root, 0)

  return result
}