二叉树的最大深度
Maximum Depth of Binary Tree
返回二叉树的最大深度，即根节点到最远叶子节点的节点数。
在力扣中练习题目描述
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3
示例 2：
输入：root = [1,null,2] 输出：2
提示：
- 树中节点的数量在
[0, 104]区间内。 -100 <= Node.val <= 100
解题思路
主解法
后序递归 · 子树高度
空树高度 0，当前节点高度 = 1 + 左右较大的高度
树是递归定义的：一棵树的高度，等于左子树高度和右子树高度中较大的那个再加 1。空树高度为 0。
因此先递归求左右子树，等两个结果都回来后再合成当前节点。画面上绿色的节点是已经算完的，箭头表示把高度返回给父节点。
分步图解
递归会先走到叶子，再从下往上返回高度；空节点返回 0。
后序计算高度 · 绿色已算完
自拟树的左子树有 5 → 3 → 2 → 1 这条长链，右子树只有 5 → 8 → 7/9。根节点不能只沿着一条路走到底，必须比较左右两边。
分步图解
节点 8：左高 1，右高 1，返回 2 给父节点 5。
- left
- 1
- right
- 1
- depth
- 2
后序计算高度 · 绿色已算完
每个节点只访问一次，时间 O(n)；递归深度等于树高，最坏 O(n)。
时间 O(n)空间 O(h) 递归栈
易错点
- 把高度定义成边数：本题按节点数算，根节点高度为 1。
- 只取左子树或只取右子树：退化成求某一条路径。
- 空树没有单独处理：递归会在空指针处崩溃。
对照解法
层序遍历 · BFS
一层一层数，队列空了就是深度
时间同为 O(n)，但需要 O(宽度) 的队列；递归版只占 O(h) 栈。
用队列做层序遍历，每轮先记下当前层的节点数，把这层的节点全部弹出，同时把下一层孩子入队；每处理完一层，深度加一。
这种方法不依赖递归，适合树很深、递归可能溢出的场景；代价是需要队列保存一整层节点，最坏宽度可达 O(n)。
两种写法得到的高度定义完全相同：根所在层为第 1 层，队列循环执行的轮数就是最大深度。
- 1根节点入队，depth = 0。
- 2每轮锁定当前层大小，弹出整层并压入孩子。
- 3每完成一层 depth++。
- 4队列空时返回 depth。
时间 O(n)空间 O(宽度)
易错点
- 没有锁定当前层大小：新入队的孩子会被当成同一层，深度少算。
- 空树直接入队：队列里出现空指针。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
演示输入
root = [5,3,8,2,4,7,9,1]递归会先走到叶子，再从下往上返回高度；空节点返回 0。
后序计算高度 · 绿色已算完
查看 C++ 代码
延伸阅读
- 树的高度、直径、平衡判断都依赖“左右子树结果合成当前节点”的后序思路。
- 递归深度等于树高；极端链状树要留意栈溢出。