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

这道题到底在问什么

输入

root=[8,3,10,1,6,null,14,...]

输出

7(|8−1|=7)

最优解：一步一步想明白

1. 3记住「下行传 lo/hi、到叶子算 hi 减 lo 取最大」,下面每帧都在套它。
2. 4best = 0开局把最大差 best 记成 0。DFS 从根出发,一路把这条路径的 min、max 带下去。
3. 5访问 40从根 40 出发(紫色)。这条路径的 min 和 max 一开始都记成根的值 40。
4. 6lo=40, hi=40把 40 纳入这条路径:min 更新为 40、max 更新为 40。它还有孩子,带着新的 min、max 继续往下。
5. 7访问 20沿路径走到节点 20(紫色)。在纳入它之前,这条路径上的 min 是 40、max 是 40。
6. 8lo=20, hi=40把 20 纳入这条路径:min 更新为 20、max 更新为 40。它还有孩子,带着新的 min、max 继续往下。
7. 9访问 10沿路径走到节点 10(紫色)。在纳入它之前,这条路径上的 min 是 20、max 是 40。
8. 10lo=10, hi=40把 10 纳入这条路径:min 更新为 10、max 更新为 40。它没有孩子,是叶子,下一步算这条路径的极差。
9. 11极差 40−10=30到达叶子 10。这条根到叶路径的 max 是 40、min 是 10,极差 = 40 − 10 = 30。
10. 12best = 30极差 30 比之前的最大差大,刷新 best = 30(这条路径暂时领先)。
11. 13访问 30沿路径走到节点 30(紫色)。在纳入它之前,这条路径上的 min 是 20、max 是 40。
12. 14lo=20, hi=40把 30 纳入这条路径:min 更新为 20、max 更新为 40。它没有孩子,是叶子,下一步算这条路径的极差。
13. 15极差 40−20=20到达叶子 30。这条根到叶路径的 max 是 40、min 是 20,极差 = 40 − 20 = 20。
14. 16best = 30极差 20 没超过当前最大差 30,best 保持不变。
15. 17访问 70沿路径走到节点 70(紫色)。在纳入它之前,这条路径上的 min 是 40、max 是 40。
16. 18lo=40, hi=70把 70 纳入这条路径:min 更新为 40、max 更新为 70。它还有孩子,带着新的 min、max 继续往下。
17. 19访问 60沿路径走到节点 60(紫色)。在纳入它之前,这条路径上的 min 是 40、max 是 70。
18. 20lo=40, hi=70把 60 纳入这条路径:min 更新为 40、max 更新为 70。它没有孩子,是叶子,下一步算这条路径的极差。
19. 21极差 70−40=30到达叶子 60。这条根到叶路径的 max 是 70、min 是 40,极差 = 70 − 40 = 30。
20. 22best = 30极差 30 没超过当前最大差 30,best 保持不变。
21. 23访问 90沿路径走到节点 90(紫色)。在纳入它之前,这条路径上的 min 是 40、max 是 70。
22. 24lo=40, hi=90把 90 纳入这条路径:min 更新为 40、max 更新为 90。它没有孩子,是叶子,下一步算这条路径的极差。
23. 25极差 90−40=50到达叶子 90。这条根到叶路径的 max 是 90、min 是 40,极差 = 90 − 40 = 50。
24. 26best = 50极差 50 比之前的最大差大,刷新 best = 50(这条路径暂时领先)。
25. 27答案 = 50四条根到叶路径的极差分别是 30、20、30、50,最大的来自 40→70→90 这条(max 90、min 40)。所以答案是 50。整趟只做了一次 DFS、每个节点访问一次。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        def dfs(node, lo, hi):
            if not node:
                return hi - lo
            lo, hi = min(lo, node.val), max(hi, node.val)
            return max(dfs(node.left, lo, hi), dfs(node.right, lo, hi))
        return dfs(root, root.val, root.val)

#include <algorithm>
#include <climits>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution { public: int maxAncestorDiff(TreeNode* root){ function<int(TreeNode*,int,int)> dfs=[&](TreeNode* n,int lo,int hi){ if(!n)return hi-lo; lo=min(lo,n->val); hi=max(hi,n->val); return max(dfs(n->left,lo,hi),dfs(n->right,lo,hi)); }; return dfs(root,root->val,root->val); } };

import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}
class Solution { public int maxAncestorDiff(TreeNode root){ return dfs(root,root.val,root.val); } int dfs(TreeNode n,int lo,int hi){ if(n==null)return hi-lo; lo=Math.min(lo,n.val); hi=Math.max(hi,n.val); return Math.max(dfs(n.left,lo,hi),dfs(n.right,lo,hi)); } }

复杂度

面试官可能追问