算法刷题系列（二十七）：二叉树——从节点关系建立递归模型

算法刷题系列（二十七）：二叉树——从节点关系建立递归模型

二叉树由节点和左右孩子关系组成。面对树题，容易被“每个节点都要处理”带偏；更可靠的起点是定义一个递归函数：它接收当前子树，返回一个明确结果。本文以求最大深度为例，说明递归定义、空树基例和归纳证明如何配合。

一、从结构写出递推关系

若当前节点为空，它的深度为 0。非空节点的最长根到叶路径必须先经过左子树或右子树之一，因此：

depth(node) = 1 + max(depth(node.left), depth(node.right))

例子中，根节点有左子树深度 2、右子树深度 3，那么整棵树深度为 1 + max(2, 3) = 4。这里深度按节点数计；若题目按边数计，空树或叶子节点的基准值会不同，必须先统一定义。

二、递归的正确性与不变式

对树的高度归纳：空树直接返回 0，定义成立。假设左右子树的递归结果分别正确，那么从当前根出发的最长路径只能进入其中一棵子树；取较大者再加上根节点，便得到当前树的正确深度。每次递归严格进入更小的子树，最终到达空孩子，因此会终止。

三、Java 实现

public class Main {
    static final class Node {
        final int value;
        Node left;
        Node right;

        Node(int value) {
            this.value = value;
        }
    }

    static int maxDepth(Node node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.right = new Node(4);
        root.right.left = new Node(5);
        root.right.left.left = new Node(6);
        assert maxDepth(root) == 4;
        assert maxDepth(null) == 0;
    }
}

四、Python 实现

from typing import Optional

class Node:
    def __init__(
        self, value: int, left: "Node | None" = None, right: "Node | None" = None
    ) -> None:
        self.value = value
        self.left = left
        self.right = right

def max_depth(node: Optional[Node]) -> int:
    if node is None:
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))

root = Node(1, Node(2, None, Node(4)), Node(3, Node(5, Node(6))))
assert max_depth(root) == 4
assert max_depth(None) == 0

五、复杂度与边界

每个节点只访问一次，时间复杂度 O(n)；递归调用栈为 O(h)，h 是树高。平衡树的栈深约 O(log n)，极度偏斜的树可能达到 O(n)，在语言栈较小或输入很深时应考虑显式栈或队列实现。

• 空树深度为 0；单节点深度为 1。
• 代码假设输入是真正的树：每个孩子最多只有一个父节点且无环。共享子节点或环结构不是普通二叉树，直接递归可能重复计算甚至不终止。
• maxDepth 与 minDepth 的空孩子处理不能简单混淆：最小深度必须确保到达叶子，而不能把缺失孩子当作一条更短的根叶路径。

常见错误是只递归左子树，或在非空节点漏掉 +1；也有人在处理叶子时另写特判，反而使基例重复。先确定函数“返回什么”，再按节点关系推导组合公式，通常更稳。

小结与衔接

递归模型由子问题含义、空结构基例和组合关系构成。最大深度只用到孩子结果；遍历问题则要求确定“何时访问当前节点”。下一篇把前序、中序、后序与层序放在同一节点模型中比较。