1026. 节点与其祖先之间的最大差值 - 力扣（LeetCode）

---

给定二叉树的根节点 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

---

方法一：「递」

V=∣A.val−B.val∣，要是V尽可能的大，分类讨论：

      ① 如果 A.val < B.val ，那么 A.val 越小，V 越大

      ② 如果 A.val >= B.val ，那么 A.val 越大，V 越大

故，无需记录递归路径中的全部节点值，只需记录递归路径中的最小值 minV 和 最大值 maxV

        - minV = min(minV,B.val);

        - maxV = max(maxV,B.val);

每递归到一次节点B，计算： max(∣minV−B.val∣,∣maxV−B.val∣)

由于 minV <= B.val <= maxV ，上式可化简为：max(B.val−minV,maxV−B.val)

并更新答案的最大值：ans = max(ans,max(B.val - minV,maxV - B.val));

// 方法一：自顶向下
class Solution {
public:
    int ans = 0;
    void dfs(TreeNode* node,int minV,int maxV) {
        if(node == nullptr) return;
        minV = min(minV,node->val);
        maxV = max(maxV,node->val);
        ans = max(ans,max(node->val - minV,maxV - node->val));
        dfs(node->left,minV,maxV);
        dfs(node->right,minV,maxV);
    }
    int maxAncestorDiff(TreeNode* root) {
        dfs(root, root->val, root->val);
        return ans;
    }
};

优化：对于一条从根出发向下的路径，实际上算的是这条路径上任意两点的最大差值

递归到叶子时，minV 和 maxV是从根到叶子的路径上的最小值和最大值，那么从根到叶子的路径上任意两点的最大差值：maxV - minV 。所以无需每个节点都去更新答案，在递归到终点时才去更新答案

// 方法一：自顶向下
class Solution {
public:
    int ans = 0;
    void dfs(TreeNode* node,int minV,int maxV) {
        if(node == nullptr) {
            ans = max(ans,maxV-minV);
            return;
        }
        minV = min(minV,node->val);
        maxV = max(maxV,node->val);
        
        dfs(node->left,minV,maxV);
        dfs(node->right,minV,maxV);
    }
    int maxAncestorDiff(TreeNode* root) {
        dfs(root, root->val, root->val);
        return ans;
    }
};

方法二：「归」

int minV=node->val,maxV=minV;
minV = min(minV,min(minLV,minRV));
maxV = max(maxV,max(maxLV,maxRV));
ans = max(ans,max(node->val - minV,maxV - node->val));

// 自底向上
class Solution {
public:
    int ans = 0;
    pair<int,int> dfs(TreeNode* node) {
        if(node == nullptr) return {INT_MAX, INT_MIN};
        int minV=node->val,maxV=minV;
        auto [minLV,maxLV] = dfs(node->left);                                  
        auto [minRV,maxRV] = dfs(node->right);
        minV = min(minV,min(minLV,minRV));
        maxV = max(maxV,max(maxLV,maxRV));
        ans = max(ans,max(node->val - minV,maxV - node->val));
        return {minV,maxV};
    }
    int maxAncestorDiff(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

参考和推荐文章：

1026. 节点与其祖先之间的最大差值 - 力扣（LeetCode）https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor/solutions/2232367/liang-chong-fang-fa-zi-ding-xiang-xia-zi-wj9v/