跳到主要内容

104. 二叉树的最大深度

题目描述​

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

示例 1

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

输出：3

示例 2：

输入：root = [1,null,2]

输出：2

示例 3：

输入：root = []

输出：0

提示：

  • 树中节点的数量在 [0, 104] 区间内
  • -100 <= Node.val <= 100

出处：LeetCode

解法一：递归​

思路​

递归遍历二叉树，计算左右子树的最大深度，取最大值加上根节点的深度。

实现​

function maxDepth(root: TreeNode | null): number {
  if (root === null) {
    return 0;
  }
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

复杂度分析​

  • 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点在递归中只被遍历一次。
  • 空间复杂度：O(n)，其中 n 是二叉树的节点数。递归函数的调用栈的深度等于二叉树的高度，最坏情况下二叉树的高度等于节点数。

解法二：迭代​

思路​

我们可以使用广度优先搜索（BFS）来计算二叉树的最大深度。

实现​

function maxDepth(root: TreeNode | null): number {
  if (root === null) {
    return 0;
  }
  const queue: TreeNode[] = [root];
  let depth = 0;
  while (queue.length > 0) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift()!;
      if (node.left !== null) {
        queue.push(node.left);
      }
      if (node.right !== null) {
        queue.push(node.right);
      }
    }
    depth++;
  }
  return depth;
}

复杂度分析​

  • 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点在广度优先搜索中只被遍历一次。
  • 空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度取决于队列的大小，队列的大小不会超过二叉树的宽度，最坏情况下二叉树的宽度等于节点数。

解法三：深度优先搜索​

思路​

我们可以使用深度优先搜索（DFS）来计算二叉树的最大深度。

实现​

function maxDepth(root: TreeNode | null): number {
  if (root === null) {
    return 0;
  }
  const stack: [TreeNode, number][] = [[root, 1]];
  let depth = 0;
  while (stack.length > 0) {
    const [node, curDepth] = stack.pop()!;
    depth = Math.max(depth, curDepth);
    if (node.right !== null) {
      stack.push([node.right, curDepth + 1]);
    }
    if (node.left !== null) {
      stack.push([node.left, curDepth + 1]);
    }
  }
  return depth;
}

复杂度分析​

  • 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点在深度优先搜索中只被遍历一次。
  • 空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度取决于栈的大小，栈的大小不会超过二叉树的高度，最坏情况下二叉树的高度等于节点数。