LC104　二叉树的最大深度¶

简单通过率 79%python3核心代码模式二叉树样例通过牛客 AC树深度优先搜索广度优先搜索二叉树

一句话

按层向下推进，能推进多少层，最大深度就是多少。

解题思路¶

这题考什么¶

最大深度 = 从根到最远叶子的路径上的节点数。教科书写法是一行递归「1 + max(左子树深度, 右子树深度)」，思路本身没问题，问题出在规模上：节点数可以到 1e4，最坏是一条链，递归深度就是 1e4，远超 CPython 默认的 1000 层上限，直接 RecursionError；递归改迭代见 DFS 深度优先搜索的 60.4 节。

换成广度优先搜索（BFS）就没有这个问题：手里握着「当前层的全部节点」，用它们的孩子拼出下一层，每处理一层计数加一。能推进出多少个非空层，最大深度就是多少 —— 因为最深的那个叶子，必定落在最后一个非空层里。递归的深度被搬到了堆上的列表长度，列表想多长有多长。

示例 1 的 [3,9,20,null,null,15,7]：

[3]     -> depth 1，孩子拼出 [9, 20]
[9,20]  -> depth 2，孩子拼出 [15, 7]
[15,7]  -> depth 3，两个叶子没有孩子，下一层为空，结束

返回 3，与样例一致。

数据规模与复杂度¶

节点数在 [0, 10^4]，节点值在 [-100, 100]（值与答案无关，只有形状有关）。每个节点入列表一次、被展开一次，时间 O(n)；空间是最宽一层的节点数，完全二叉树下约 n/2，量级 O(n)。

坑在哪¶

空树返回 0。题面节点数下界是 0，不先判空的话第一轮就会对 None 取 .left，而且深度会凭空多算一层。
n 到 1e4 且允许链状树，所以不能写递归。这是本题唯一的实现性约束，其余部分怎么写都对。
计数加在本层被处理时，不是在拼出非空的下一层之后。若改成「拼出了非空的下一层才加一」，单节点树会返回 0。
深度按节点数算，不是边数。同专题 LC543 的直径按边数算，两者差一，口径混用会让答案整体偏一。

参考实现¶

solutions/leetcode/LC104/sol.py
from typing import List, Optional


class Solution:
    def maxDepth(self, root: "Optional[TreeNode]") -> int:
        # 空树深度为 0；这一句同时保证 level 里不会混进 None
        if root is None:
            return 0
        depth = 0
        # 循环不变量：level 是当前层的全部节点，depth 是它上面已经数过的层数
        level = [root]
        while level:
            # 本层存在，深度先加一 —— 深度按节点数算，根所在的那层就是第 1 层
            depth += 1
            # 用本层的孩子拼出下一层；左右先后对本题的答案没有影响
            nxt: List["TreeNode"] = []
            for node in level:
                if node.left is not None:
                    nxt.append(node.left)
                if node.right is not None:
                    nxt.append(node.right)
            level = nxt
        # 最后一个非空层的层号，就是最远叶子所在的层
        return depth

LC104 二叉树的最大深度¶