SlovinG
Search K

Appearance

104.二叉树的最大深度 ​

难度：容易

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

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

示例 1：

img

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

示例 2：

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

提示：

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

层序遍历+队列法 ​

这道题和 102 题非常类似，只不过在单层遍历的时候记录一下当前深度就可以了。

层序遍历一个二叉树。就是从左到右、一层一层地去遍历二叉树。这种遍历的方式需要借用一个辅助数据结构即队列来实现。

队列具有 先进先出 的特性，符合层序遍历的逻辑。这种层序遍历的方式就是图论中的广度优先遍历，只不过我们应用在了二叉树上。

算法流程：

  1. 处理特例：若根节点为空，则返回 0
  2. 根节点入队
  3. BFS 循环： 判断队列是否为空。如果不为空，说明还有节点需要遍历
    1. 初始化当前层的节点个数 currentLevelSize 为队列的大小。
    2. 深度增加。
    3. 使用一个内层循环，遍历当前层的节点。循环次数为当前层的节点个数 currentLevelSize。

      1. 如果当前节点有左子节点，将左子节点入队。

      2. 如果当前节点有右子节点，将右子节点入队。

    4. 此时队列中已经把当前层的节点都出队了，同时把下一层的节点都入队了，因此队列大小刚好变成了下一层的节点个数。
  4. 返回深度值：当所有层都遍历完毕后，此时得到的深度值代表的就是最深的那一层。

代码展示 ​

java
public int maxDepth(TreeNode root) {
    // 若根节点为空，则返回0
    if (root == null) {
        return 0;
    }
    int depth = 0;
    Deque<TreeNode> queue = new LinkedList<>();
    // 根节点入队
    queue.add(root);
    // BFS 循环
    while (!queue.isEmpty()) {
        int currentLayerSize = queue.size();
        // 深度增加
        depth++;
        // 这里一定要使用固定大小currentLayerSize，不要使用queue.size()，因为queue不停地出队入队，所以其大小是不断变化的
        for (int i = 0; i < currentLayerSize; i++) {
            TreeNode current = queue.poll();
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
    }
    return depth;
}

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，最差情况下，即当树为满二叉树时，最多有 (n+1)/2 个树节点 同时 在 queue 中，故使用 O(n) 大小的额外空间。

递归法 ​

递归法的核心思想是，二叉树的最大深度等于其左右子树深度的最大值加一（加的这个一代表根节点本身）。

代码展示 ​

java
public int maxDepth(TreeNode root) {
    // 如果当前节点为空，意味着深度为0
    if (root == null) {
        return 0;
    }
    // 递归求左子树的深度
    int leftDepth = maxDepth(root.left);
    // 递归求右子树的深度
    int rightDepth = maxDepth(root.right);
    // 当前树的最大深度为左右子树深度的最大值 + 1（根节点自身）
    return Math.max(leftDepth, rightDepth) + 1;
}

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(1)，因为这种做法没有使用队列，所以大大降低了空间复杂度。

总结 ​

这份代码可以作为二叉树层序遍历的模板。