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

约 7 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节跳动 猿辅导
标签
深度优先搜索 树 二叉树
目录

题目描述

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

题意分析

给一棵二叉树，要在所有满足「a 是 b 的祖先」的节点对里，找出 |a.val - b.val| 的最大值。

「祖先」这个限定是核心约束：两个节点必须落在同一条从根往下的链上，分属左右两棵子树的节点即使差值很大也不能配对。所以答案一定诞生于某条根到叶的路径内部。

另一个信号是求的是绝对差，而不是有向的差。这意味着不用关心谁在上谁在下，只关心一条链上出现过的数值范围有多宽。

规模上节点数最多几千，值域非负且有上界，所以不必担心溢出；题目保证树至少有两个节点，但代码里对空树给个兜底返回更稳妥。

解法：DFS 维护路径最大最小值

核心思路

暴力做法是枚举每个节点，再向上遍历它所有祖先逐一比较。但二叉树节点没有父指针，得先建一张父表；即便建好了，一条长链上第 k 个节点要回溯 k 次，退化成链时总代价是 $O(n^2)$。瓶颈在于同一段祖先被反复扫描。

换个角度：与其让每个节点回头找祖先，不如在往下走的过程中把祖先信息一路带下来。祖先集合沿着根到当前节点的路径只增不减，是一个纯粹的追加过程。

再观察一步，某个节点 b 与它全部祖先的最大绝对差，只取决于祖先里的最小值和最大值两个数，中间那些值永远不可能成为最优。既然只需要两个数，就不必存整条链。

不变量：递归进入节点 node 时，参数 minVal 与 maxVal 恰好是根到 node 这条路径上（含 node 的父节点，更新后含 node 自身）所有节点值的最小值与最大值。 由此，走到空指针处时 maxVal - minVal 就是这条完整根到叶路径能贡献的最大差值，整棵树的答案是所有这类值的最大者。

解题步骤

  • 根为空直接返回 0。题目虽然保证树非空，但这条兜底让递归入口不必特判。
  • 以 dfs(root, root.val, root.val) 启动。把初值都设成根值，是为了让不变量从第一层就成立，避免用哨兵极值导致首次差值被算大。
  • 递归到空节点时返回 maxVal - minVal。此时路径已经走满，这个差值就是该路径上「最大值节点」和「最小值节点」这一对的绝对差；它们必然一个是另一个的祖先，因为同在一条链上。
  • 非空节点先用自身值更新 minVal 和 maxVal，再递归左右子树。顺序不能反：当前节点既可能当祖先也可能当后代，必须先并入路径边界，传给子树的信息才完整。
  • 返回左右两侧结果的较大者。差值最大的那一对必定落在某条具体路径上，取所有路径的最大值即为全局答案。

以 [8,3,10,1,6,null,14,null,null,4,7,13] 走一遍：树形是根 8，左子树根 3（左 1，右 6，6 的左右为 4 和 7），右子树根 10（右子 14，14 的左子 13）。入口 dfs(8, 8, 8)，更新后 min = 8、max = 8。左侧进入 dfs(3, 8, 8)，更新为 min = 3、max = 8；再进 dfs(1, 3, 8) 更新为 min = 1、max = 8，它的两个空孩子都返回 8 - 1 = 7，故该支返回 7。回到 3 的右侧 dfs(6, 3, 8)，6 不改变边界，其左 dfs(4, 3, 8) 边界仍是 3 和 8，空孩子返回 5；右 dfs(7, 3, 8) 同样返回 5，故 6 这一支返回 5。于是 3 返回 max(7, 5) = 7。右侧 dfs(10, 8, 8) 更新为 min = 8、max = 10，左孩子为空返回 2；右 dfs(14, 8, 10) 更新为 max = 14，其左 dfs(13, 8, 14) 不改变边界，空孩子返回 6，右孩子为空也返回 6，故 14 返回 6，10 返回 max(2, 6) = 6。根返回 max(7, 6) = 7，对应节点对 (8, 1)。

代码实现

class Solution {
    public int maxAncestorDiff(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return dfs(root, root.val, root.val);
    }

    private int dfs(TreeNode node, int minVal, int maxVal) {
        if (node == null) {
            return maxVal - minVal;
        }

        // minVal 和 maxVal 始终表示根到当前路径上的最小值与最大值。
        minVal = Math.min(minVal, node.val);
        maxVal = Math.max(maxVal, node.val);

        int left = dfs(node.left, minVal, maxVal);
        int right = dfs(node.right, minVal, maxVal);
        return Math.max(left, right);
    }
}

func maxAncestorDiff(root *TreeNode) int {
    if root == nil {
        return 0
    }

    var dfs func(node *TreeNode, minVal int, maxVal int) int
    dfs = func(node *TreeNode, minVal int, maxVal int) int {
        if node == nil {
            return maxVal - minVal
        }

        // minVal 和 maxVal 始终表示根到当前路径上的最小值与最大值。
        if node.Val < minVal {
            minVal = node.Val
        }
        if node.Val > maxVal {
            maxVal = node.Val
        }

        left := dfs(node.Left, minVal, maxVal)
        right := dfs(node.Right, minVal, maxVal)
        if left > right {
            return left
        }
        return right
    }

    return dfs(root, root.Val, root.Val)
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点恰好进入递归一次，节点内部只做常数次比较，没有任何回溯扫描祖先的动作。
  • 空间复杂度：$O(h)$，其中 $h$ 为树高，仅由递归调用栈贡献；树退化成链时最坏为 $O(n)$，完全二叉树时为 $O(\log n)$。

关键点总结

  • 「节点与祖先」类问题的通用手法是自顶向下传递路径摘要，而不是自底向上回溯查找祖先，前者天然把重复扫描消掉。
  • 判断需要传什么信息，要看目标函数依赖祖先集合的哪些统计量。这里只依赖极值，所以两个 int 就够；如果改成求路径上第 k 大，才需要更重的结构。
  • 把答案的收集点放在空指针处，是一种让叶子无需特判的技巧：叶子的两个空孩子会自动返回同一个值，取最大后不影响正确性。
  • 面试视角：先说 $O(n^2)$ 的父指针回溯法，再指出重复扫描是瓶颈，最后给出 $O(n)$ 的传参解法，比直接甩答案更能展示优化路径。
  • 面试视角：常见追问是「能否改成后序返回子树极值」。可以答：也能做，让每个节点返回子树内的最小最大值，在父节点处更新答案，复杂度相同；但自顶向下的版本参数含义更直白，白板上不易写错。

易错点总结

  • 错误写法：把 minVal 初始化为 Integer.MAX_VALUE、maxVal 初始化为 Integer.MIN_VALUE 却仍在空节点处返回差值。用例任意树 → 一旦某个节点的空孩子在边界尚未被任何真实值覆盖前被访问，相减会直接溢出成负数或荒谬的大数。
  • 错误写法：先递归左右子树，再更新 minVal 和 maxVal。用例 [8,3,10,1,...] → 节点 1 的边界里不含 1 自己，路径 8 → 3 → 1 只会算出 8 - 3 = 5，答案偏小。
  • 错误写法：只在叶子节点处收集答案，判空写成 if (node.left == null && node.right == null) 却忘了先判 node == null。用例根只有左孩子的树 → 递归进入空的右孩子时直接空指针异常。
  • 错误写法：把左右子树的结果相加或取最小。用例 [8,3,10,1,6,null,14,null,null,4,7,13] → 相加得到远大于 7 的虚假值，取最小则得到 5，两者都不是合法的祖先对差值。
  • 错误写法：把 minVal、maxVal 提成成员变量而不在回溯时还原。用例左右子树数值范围差异大的树 → 右子树会继承左子树留下的边界，把跨分支的两个节点错配成祖先对，结果偏大。
  • 错误写法：用 node.val - minVal 和 maxVal - node.val 在每个节点即时更新全局答案，却把更新放在并入自身之前。用例只有两层的树 → 根节点处两个差值都是 0，等于漏掉了根与孩子这一对。
  • 错误写法：认为答案一定出现在根与某个叶子之间，于是只比较 root.val 与各叶子值。用例 [8,3,10,1,6,null,14,null,null,4,7,13] 中若把根改成 5 → 真实最大差来自 10 与 13 这类非根祖先对，只看根会算错。
  • 错误写法：返回值类型用 int 但先做 Math.abs(maxVal - minVal) 之外的额外取绝对值，或反过来写成 minVal - maxVal。用例任意树 → 得到恒为负的结果，最终答案变成 0 或负数。

相似题目

题目 难度 考察点
1448. 统计二叉树中好节点的数目 中等 同样自顶向下传路径极值，但只需最大值且求计数
112. 路径总和 简单 传递的是路径累加和，且需在叶子处判定命中
543. 二叉树的直径 简单 自底向上返回子树高度，答案在节点处横向合并
124. 二叉树中的最大路径和 困难 路径可跨越左右子树，需处理负贡献剪枝
530. 二叉搜索树的最小绝对差 简单 利用中序有序性比较相邻值，与祖先关系无关