节点与其祖先之间的最大差值

记住「下行传 lo/hi、到叶子算 hi 减 lo 取最大」,下面每帧都在套它。

准备 · 从根出发：开局把最大差 best 记成 0。DFS 从根出发,一路把这条路径的 min、max 带下去。

下行 · 到达 40：从根 40 出发(紫色)。这条路径的 min 和 max 一开始都记成根的值 40。

纳入 40：把 40 纳入这条路径:min 更新为 40、max 更新为 40。它还有孩子,带着新的 min、max 继续往下。

下行 · 到达 20：沿路径走到节点 20(紫色)。在纳入它之前,这条路径上的 min 是 40、max 是 40。

纳入 20：把 20 纳入这条路径:min 更新为 20、max 更新为 40。它还有孩子,带着新的 min、max 继续往下。

下行 · 到达 10：沿路径走到节点 10(紫色)。在纳入它之前,这条路径上的 min 是 20、max 是 40。

纳入 10：把 10 纳入这条路径:min 更新为 10、max 更新为 40。它没有孩子,是叶子,下一步算这条路径的极差。

叶子 10 · 算极差：到达叶子 10。这条根到叶路径的 max 是 40、min 是 10,极差 = 40 − 10 = 30。

叶子 10 · 刷新 best：极差 30 比之前的最大差大,刷新 best = 30(这条路径暂时领先)。

下行 · 到达 30：沿路径走到节点 30(紫色)。在纳入它之前,这条路径上的 min 是 20、max 是 40。

纳入 30：把 30 纳入这条路径:min 更新为 20、max 更新为 40。它没有孩子,是叶子,下一步算这条路径的极差。

叶子 30 · 算极差：到达叶子 30。这条根到叶路径的 max 是 40、min 是 20,极差 = 40 − 20 = 20。

叶子 30 · best 不变：极差 20 没超过当前最大差 30,best 保持不变。

下行 · 到达 70：沿路径走到节点 70(紫色)。在纳入它之前,这条路径上的 min 是 40、max 是 40。

纳入 70：把 70 纳入这条路径:min 更新为 40、max 更新为 70。它还有孩子,带着新的 min、max 继续往下。

下行 · 到达 60：沿路径走到节点 60(紫色)。在纳入它之前,这条路径上的 min 是 40、max 是 70。

纳入 60：把 60 纳入这条路径:min 更新为 40、max 更新为 70。它没有孩子,是叶子,下一步算这条路径的极差。

叶子 60 · 算极差：到达叶子 60。这条根到叶路径的 max 是 70、min 是 40,极差 = 70 − 40 = 30。

叶子 60 · best 不变：极差 30 没超过当前最大差 30,best 保持不变。

下行 · 到达 90：沿路径走到节点 90(紫色)。在纳入它之前,这条路径上的 min 是 40、max 是 70。

纳入 90：把 90 纳入这条路径:min 更新为 40、max 更新为 90。它没有孩子,是叶子,下一步算这条路径的极差。

叶子 90 · 算极差：到达叶子 90。这条根到叶路径的 max 是 90、min 是 40,极差 = 90 − 40 = 50。

叶子 90 · 刷新 best：极差 50 比之前的最大差大,刷新 best = 50(这条路径暂时领先)。

完成：四条根到叶路径的极差分别是 30、20、30、50,最大的来自 40→70→90 这条(max 90、min 40)。所以答案是 50。整趟只做了一次 DFS、每个节点访问一次。

边界:单节点 0、全等 0、链就是首尾极差。

面试重点:下行传 min/max 做到 O(n);最大差必出现在路径极值这一对。