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

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

题目描述

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

image-20260928225447017

image-20260928225447018

image-20260928225447019

题意分析

在二叉树中选择具有祖先与后代关系的两个节点，使它们数值之差的绝对值最大。祖先不一定是直接父节点，可以隔着多层；两个节点也不要求包含整棵树的根。

位于不同分支、彼此没有祖先关系的节点不能配成一对。因此整棵树的最大值减最小值未必合法，需要把比较限制在同一条从根向下的路径上。

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

核心思路

[!blue]

一条从根向下的路径上，任意两个不同节点都有祖先关系。对这条路径来说，最大绝对差就是路径最大值减最小值，没必要保存所有祖先再逐一比较。

DFS 向下传递 minVal、maxVal，表示当前路径已经出现过的最小和最大值。进入一个节点时，先把它的值并入两个极值，再把更新后的范围分别传给左右孩子。

递归到空孩子时，当前路径前缀已经确定，可以返回 maxVal - minVal。空孩子不一定出现在叶子之后，但这个路径前缀本身仍然合法；继续向其他孩子延伸只会保持或扩大极差，不会让此前贡献变成非法值。

左右递归各自给出本分支能达到的最大差，当前层取两者较大值即可。不能把左右极值合并后相减，否则又会混入没有祖先关系的跨分支节点。

每一对合法祖先和后代都处于某条根到叶路径中，而每条路径的极值差又确实来自一对合法节点，所以遍历全部分支后取最大极差，既不会漏掉答案，也不会引入非法配对。

解题步骤

  1. 代码先处理空根；非空时用根值初始化路径最小值和最大值。
  2. 到达真实节点后，更新当前路径极值，把该节点纳入范围。
  3. 用这两个值分别递归左右孩子；空孩子直接返回当前极差。
  4. 每层返回左右结果中的较大值，最终根调用的返回值就是答案。

代码实现

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 = 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
        }

        // 先并入当前节点，再把独立的路径极值传给子树。
        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)$，递归栈深度等于树高；链状树最坏为 $O(n)$，没有保存所有祖先的额外列表。

关键点总结

[!green]

  • 用路径最大值和最小值压缩祖先信息，足以求该路径的最大绝对差。
  • 极值通过数值参数传递，左右分支拿到各自的路径状态，不需要回滚共享变量。
  • 分支结果取最大，分支极值不混合，始终保持祖先关系约束。

易错点总结

[!yellow]

  • 把整棵树的全局最大值减最小值，可能选中两条不同分支上的节点。
  • 只比较父子差值，会漏掉隔着多层的祖先与后代。
  • 传给孩子之前不加入当前值，可能漏掉路径中间的关键极值。
  • 用不恢复的全局极值保存路径，会把先访问分支的值带入另一分支。
  • 将左右返回值相加，不能对应任何一对节点；题目求一个最大差，应取最大值。

相似题目

题目 难度 关联与区别
1448. 统计二叉树中好节点的数目 中等 同样沿根路径下传极值，原题只需祖先最大值，本题同时保留最小与最大值计算最大差。
112. 路径总和 简单 同样把路径相关信息作为递归参数，本题传极值，原题传累计和或剩余目标。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/82069309
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！