二叉树递归：最大深度、前序遍历与直径

二叉树的很多问题都可以通过递归解决，但不同题目的递归写法并不完全相同。

我觉得理解二叉树递归时，可以从两个角度考虑：

• 分解子问题：先让左右子树分别解决自己的问题，再利用它们返回的结果计算当前节点的答案。
• 遍历整棵树：按照一定顺序访问每个节点，在遍历过程中维护状态、更新结果。

下面结合三道 LeetCode 题目，看看这两种思路具体有什么区别。

1. LeetCode 104. 二叉树的最大深度

题目要求计算一棵二叉树的最大深度，也就是从根节点到最远叶子节点的最长路径所经过的节点数。

这道题可以使用两种递归思路来解决。

1.1 分解子问题

先从一棵树本身考虑。

假设已经知道左子树和右子树的最大深度，那么整棵树的最大深度，就是两者中的较大值再加一。

因此，可以得到递推关系：

这里加上的 1，代表当前根节点本身。

接下来只需要让左右子树分别计算自己的最大深度。对于每棵子树，又可以采用同样的方法继续递归。

那么，递归什么时候结束呢？

当遇到空节点时，它的深度为 0，直接返回即可。

Python 代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        leftmax = self.maxDepth(root.left)
        rightmax = self.maxDepth(root.right)
        return 1 + max(leftmax, rightmax)

这份代码的逻辑比较直观：

1. 遇到空节点，返回 0。
2. 递归计算左子树的最大深度。
3. 递归计算右子树的最大深度。
4. 取两者的较大值，再加上当前节点，作为整棵子树的最大深度返回。

这里有一个值得注意的地方：当前节点必须先得到左右子树的返回值，才能计算自己的最大深度。

因此，虽然代码从根节点开始递归，但真正计算当前节点深度的操作发生在左右子树处理完成之后，属于后序位置的处理。

1.2 遍历整棵树

除了让子树返回深度，还可以换一种思路：直接遍历整棵树，并在遍历过程中记录当前深度。

这里使用两个变量：

• depth：记录当前递归路径的深度。
• res：记录遍历过程中遇到的最大深度。

每进入一个非空节点，就让 depth 加一。

当递归走到空节点时，说明当前这条路径已经走到了末尾，此时使用 depth 更新最大深度。

不过，还有一个很重要的细节：从当前节点返回上一层时，需要将 depth 减一。

因为接下来可能还要遍历另一棵子树。如果不恢复深度，左右子树的路径长度就会相互影响。

这也是递归回溯中常见的做法：进入节点时修改状态，离开节点时恢复状态。

Python 代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.depth = 0
        self.res = 0

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        self.traverse(root)
        return self.res

    def traverse(self, root):
        if root is None:
            self.res = max(self.res, self.depth)
            return
        self.depth += 1
        self.traverse(root.left)
        self.traverse(root.right)
        self.depth -= 1

与第一种方法相比，这次递归函数不需要返回子树的最大深度，而是通过 self.depth 和 self.res 维护整个遍历过程中的状态。

两种方法都需要访问整棵树，但思考方式有所不同：

• 分解子问题：当前节点的答案由左右子树的返回值决定。
• 遍历思路：沿着递归路径维护深度，在遍历过程中更新全局答案。

理解了这个区别，再来看后面的题目就会更容易一些。

2. LeetCode 144. 二叉树的前序遍历

前序遍历的访问顺序为：

根节点 → 左子树 → 右子树

也就是说，每进入一个节点，先记录它的值，再递归访问左右子树。

这道题不需要计算子树的返回值，只需要按照指定顺序访问节点，并将结果保存到列表中即可。

因此，可以使用前面介绍的遍历思路。

定义一个 res 列表保存答案，再通过 traverse() 递归访问每个节点：

1. 如果当前节点为空，直接返回。
2. 将当前节点的值加入 res。
3. 递归遍历左子树。
4. 递归遍历右子树。

Python 代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.res = []

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        self.traverse(root)
        return self.res

    def traverse(self, root):
        if root is None:
            return
        self.res.append(root.val)
        self.traverse(root.left)
        self.traverse(root.right)

这里最关键的是：

self.res.append(root.val)

它位于递归访问左右子树之前，因此当前节点的值会先被记录，这就是前序遍历。

如果将这行代码放到两次递归调用之间，就变成了中序遍历；如果放在两次递归调用之后，则是后序遍历。

所以，前序、中序和后序遍历的区别，不只是访问节点的顺序不同，也可以理解为对当前节点的操作发生在递归过程中的哪个位置。

3. LeetCode 543. 二叉树的直径

这道题要求找出二叉树中任意两个节点之间的最长路径，并返回这条路径包含的边数。

需要注意，最长路径不一定经过根节点，因此不能只计算根节点左右子树的深度之和，而是要检查每个节点。

3.1 利用子树深度计算直径

先考虑经过某一个节点的最长路径。

如果我们已经知道它左子树和右子树的最大深度，那么经过当前节点、连接左右两侧的最长路径，其边数就是：

这里不需要额外加一，因为题目要求统计的是边数，而我们的子树深度统计的是节点数。

例如，某个节点的左子树最大深度为 3，右子树最大深度为 2，那么经过这个节点的最长路径就包含 5 条边。

因此，只需要在计算每个节点最大深度的同时，用左右子树深度之和更新最大直径即可。

这就可以直接借用第 104 题中分解子问题的思路。

3.2 在后序位置更新答案

递归函数 maxDpeth() 主要完成两件事：

第一件事：计算当前节点的最大深度。

和第 104 题一样：

return 1 + max(leftMax, rightMax)

这个返回值会交给上一层递归，供父节点继续计算。

第二件事：更新整棵树的最大直径。

在得到左右子树的最大深度后，计算：

mydiameter = leftMax + rightMax

再与当前记录的最大直径比较：

self.maxdiameter = max(self.maxdiameter, mydiameter)

这里要区分清楚：递归函数返回的是深度，而 self.maxdiameter 记录的是整棵树的最大直径。

两者虽然都用到了左右子树的深度，但含义不同。

Python 代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.maxdiameter = 0

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.maxDpeth(root)
        return self.maxdiameter

    def maxDpeth(self, root):
        if root is None:
            return 0
        leftMax = self.maxDpeth(root.left)
        rightMax = self.maxDpeth(root.right)
        mydiameter = leftMax + rightMax
        self.maxdiameter = max(self.maxdiameter, mydiameter)
        return 1 + max(leftMax, rightMax)

观察代码可以发现，更新直径的操作发生在：

leftMax = self.maxDpeth(root.left)
rightMax = self.maxDpeth(root.right)

之后。

这是因为只有先递归计算完左右子树，我们才能知道经过当前节点的最长路径有多长。

因此，这道题也是典型的在后序位置利用左右子树返回值解决问题。

同时，递归会检查树中的每一个节点，确保不会遗漏那些不经过根节点的最长路径。

4. 总结

通过这三道题，可以更清楚地区分二叉树递归中的两种常见思路。

这几道题也让我对递归中的操作位置有了更清楚的认识。

前序位置是在刚进入当前节点、尚未递归处理左右子树时。此时可以利用从父节点传递下来的状态，例如当前路径的深度。

后序位置则是在左右子树都处理完成之后。此时可以获取子树返回的结果，再用这些信息计算当前节点的答案。

至于中序位置，则位于左子树处理完成、右子树尚未处理的时候。

所以，分析二叉树递归时，我觉得可以先考虑两个问题：

1. 这道题是否可以分解为左右子树的同类问题，并通过子树的返回值求出答案？
2. 还是需要遍历整棵树，在访问节点的过程中维护某种状态？

弄清楚这一点，再决定递归函数应该返回什么、操作应该放在哪个位置，代码通常就更容易写出来了。

5. 复杂度分析

这三道题都需要访问二叉树中的每个节点。

假设树有 n 个节点，高度为 h：

• 时间复杂度：均为 $O(n)$，每个节点只需要进行常数次处理。
• 递归空间复杂度：均为 $O(h)$，主要来自递归调用栈。

当二叉树比较平衡时，$h=O(\log n)$；当二叉树退化成链表时，$h=O(n)$。

另外，第 144 题还需要一个结果列表存储前序遍历的节点值，因此其结果列表会额外占用 $O(n)$ 空间。