Medium

题目描述

给定二叉树的根节点 root，找出存在于不同节点 a 和 b 之间的最大值 v，其中 v = |a.val - b.val|，且 a 是 b 的祖先。

如果 a 的任何子节点等于 b，或者 a 的任何子节点是 b 的祖先，那么我们称 a 是 b 的祖先。

示例 1：

输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释：我们有许多祖先节点和后代节点的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。

示例 2：

输入：root = [1,null,2,null,0,3]
输出：3

约束条件：

  • 树中节点数目的范围是 [2, 5000]
  • 0 <= Node.val <= 10^5

解题思路

这道题要求找到祖先与后代节点之间的最大差值。关键思路是在深度优先搜索过程中，维护从根节点到当前节点路径上的最大值和最小值。

核心思想：

  1. 对于任意一个节点，它与其子树中所有节点的最大差值，等于该节点值与子树中最大值和最小值的差值中的较大者
  2. 使用DFS遍历，在递归过程中传递当前路径上的最大值和最小值
  3. 对于每个节点，更新最大值和最小值，然后计算当前可能的最大差值

算法步骤：

  1. 从根节点开始，初始化最大值和最小值都为根节点值
  2. 对于每个节点，计算当前节点值与路径最大值、最小值的差值
  3. 更新路径上的最大值和最小值
  4. 递归处理左右子树
  5. 返回全局最大差值

这种方法只需要一次DFS遍历，时间复杂度为O(n)，空间复杂度为O(h)，其中h是树的高度。

代码实现

class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
        return dfs(root, root->val, root->val);
    }
    
private:
    int dfs(TreeNode* node, int maxVal, int minVal) {
        if (!node) return maxVal - minVal;
        
        maxVal = max(maxVal, node->val);
        minVal = min(minVal, node->val);
        
        int leftDiff = dfs(node->left, maxVal, minVal);
        int rightDiff = dfs(node->right, maxVal, minVal);
        
        return max(leftDiff, rightDiff);
    }
};

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        def dfs(node, max_val, min_val):
            if not node:
                return max_val - min_val
            
            max_val = max(max_val, node.val)
            min_val = min(min_val, node.val)
            
            left_diff = dfs(node.left, max_val, min_val)
            right_diff = dfs(node.right, max_val, min_val)
            
            return max(left_diff, right_diff)
        
        return dfs(root, root.val, root.val)

public class Solution {
    public int MaxAncestorDiff(TreeNode root) {
        return Dfs(root, root.val, root.val);
    }
    
    private int Dfs(TreeNode node, int maxVal, int minVal) {
        if (node == null) return maxVal - minVal;
        
        maxVal = Math.Max(maxVal, node.val);
        minVal = Math.Min(minVal, node.val);
        
        int leftDiff = Dfs(node.left, maxVal, minVal);
        int rightDiff = Dfs(node.right, maxVal, minVal);
        
        return Math.Max(leftDiff, rightDiff);
    }
}

var maxAncestorDiff = function(root) {
    function dfs(node, maxVal, minVal) {
        if (!node) return maxVal - minVal;
        
        maxVal = Math.max(maxVal, node.val);
        minVal = Math.min(minVal, node.val);
        
        const leftDiff = dfs(node.left, maxVal, minVal);
        const rightDiff = dfs(node.right, maxVal, minVal);
        
        return Math.max(leftDiff, rightDiff);
    }
    
    return dfs(root, root.val, root.val);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是树中节点的数量，需要访问每个节点一次
空间复杂度O(h)，其中 h 是树的高度，递归调用栈的深度