跳到主要内容

102. 二叉树的层序遍历

题目描述​

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

示例 1：

示例1

输入：root = [3,9,20,null,null,15,7]

输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]

输出：[[1]]

示例 3：

输入：root = []

输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

出处：LeetCode

解法一：递归​

思路​

递归遍历二叉树，将每个节点的值存入对应的层级数组。

实现​

function levelOrder(root: TreeNode | null): number[][] {
  const res: number[][] = [];
  const dfs = (node: TreeNode | null, level: number) => {
    if (node === null) {
      return;
    }
    if (res.length === level) {
      res.push([]);
    }
    res[level].push(node.val);
    dfs(node.left, level + 1);
    dfs(node.right, level + 1);
  };
  dfs(root, 0);
  return res;
}

复杂度分析​

  • 时间复杂度：O(N)O(N)，其中 NN 为二叉树的节点数。
  • 空间复杂度：O(N)O(N)。

解法二：迭代​

思路​

迭代遍历二叉树，使用队列存储每一层的节点。

实现​

function levelOrder(root: TreeNode | null): number[][] {
  if (root === null) {
    return [];
  }
  const res: number[][] = [];
  const queue: TreeNode[] = [root];
  while (queue.length) {
    const levelSize = queue.length;
    res.push([]);
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      res[res.length - 1].push(node.val);
      if (node.left) {
        queue.push(node.left);
      }
      if (node.right) {
        queue.push(node.right);
      }
    }
  }
  return res;
}

复杂度分析​

  • 时间复杂度：O(N)O(N)，其中 NN 为二叉树的节点数。
  • 空间复杂度：O(N)O(N)。