LeetCode 1026：节点与祖先的最大差值——自顶向下与自底向上的递归体会

最近做到了LeetCode的这一题，结合题中提到的两种解题方法 以及评论中的网友留言，有了一些对递归的深层次的感受。题解链接在此。

首先本题的核心思想是：
遍历树的过程中，我们关心的是 某个节点与路径上祖先节点的最小值和最大值的差值。因此问题可以转化为：

• 对于每个节点，维护路径上的 min 和 max。
• 计算 max - min，并在全局更新最大结果。

但是在实现上，我们可以有两种递归的方式：

方法一：自顶向下（递）

• 思路：从根节点开始，把当前路径上的最大值和最小值一路传递下去。
• 每到一个子节点，就更新 min 和 max，并递归继续往下。
• 在叶子节点处，利用路径上记录的最大值和最小值计算差值。

这种方法体现的是 前序遍历 的思想：
先把“全局情况”带下去，然后逐步收缩范围。

方法二：自底向上（归）

• 思路：站在祖先节点的角度，维护子树中的最大值和最小值。
• 递归到子树时，分别得到左子树和右子树的 min 与 max，再结合当前节点值更新。
• 最终在回溯过程中逐步更新答案。

这种方法体现的是 后序遍历 的思想：
先在底部算出子树信息，再逐层往上传递。

这样的两种思路在同一道题的体现，让我一下子就脑补出一幅画面：二叉树的根在向叶子节点传递养分， 这就是「递」； 叶子节点开花结果后把果实传回给到根（想象重力的方向是从树叶–>树根的，所以果实成熟之后 就掉在了根旁边），这就是「归」。也就正好对应评论区里两位高赞的评论： 前者是每到一个节点就更新一下状态然后把新的状态带到下一次递归中去，也就是所谓的 “先处理中间节点，再处理左右子节点” –> 前序遍历； 后者是 从子树收集信息，返回到当前节点再做处理，也就是 “先处理左右子节点，再处理中间节点” –> 后序遍历。