vvrf / DSA.log

问题拆解

题目要的是根节点到最远叶子的路径上有多少个节点。第一反应可能是去枚举所有从根到叶子的路径，比较谁最长，但这样既要记录路径又要回溯，写起来很啰嗦。

真正的关键是换一个视角：一棵树的最大深度，等于它两棵子树中较深那棵的深度，再加上根节点自己这一层。

深度这个量对整棵树的定义，和对任意子树的定义完全一样。这正是递归能生效的信号。

后序递归

先算出左右子树的深度，再合并成当前树的答案——这是典型的后序处理顺序：

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}

pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    match root {
        None => 0,
        Some(node) => {
            let node = node.borrow();
            1 + Self::max_depth(node.left.clone()).max(Self::max_depth(node.right.clone()))
        }
    }
}

空树的深度是 0，这既是递归的终点，也让叶子节点自然得到 1 + max(0, 0) = 1。整个函数几乎就是把“深度 = 较深子树 + 1”这句话原样抄成了代码。

如果担心极端瘦长的树把递归栈压爆，可以改用层序遍历，一层一层往下数，遍历了几层深度就是几。但对本题的数据规模，递归写法足够清晰。

复杂度

指标	复杂度	原因
时间	`O(n)`	每个节点恰好被访问一次
空间	`O(h)`	递归栈深度等于树高，最坏退化成 `O(n)`

可以迁移的模式

当一个量“对整体的定义”和“对局部的定义”一致时，优先考虑递归；
后序处理适合“答案要靠孩子先算好再汇总”的场景；
空节点返回一个恰当的边界值（这里是 0），能让叶子的计算无需特判。

先想清楚返回值代表什么，再写递归体，往往比先写代码再补语义顺得多。