题目描述：
给出一个二叉树根节点，找出不同的节点 $A$ 和 $B$ 之间的最大值 $V$ ，其中 $V = |A.val-B.val|$ ，且 $A$ 是 $B$ 的祖先。
数据范围：
$2\le N \le 5000;0\le node.val \le 10^5$
题解：
很明显需要使用树形dp，使用树形dp维护子树节点权重的最大值和最小值，然后用当前节点分别减去最大值最小值取绝对值更新答案。
需要注意的是如果是一个空节点，需要返回临界值，处理当前节点时要注意临界值处理。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int INF = 1e5 + 1;
struct Node
{
int minx, maxx;
};
int ans = 0;
Node dfs(TreeNode *u)
{
if (u == nullptr)
{
return {INF, -1};
}
Node left = dfs(u->left);
Node right = dfs(u->right);
Node tmp = {min(left.minx, right.minx), max(left.maxx, right.maxx)};
if (tmp.minx != INF)
ans = max(ans, abs(u->val - tmp.minx));
if (tmp.maxx != -1)
ans = max(ans, abs(u->val - tmp.maxx));
tmp.minx = min(tmp.minx, u->val);
tmp.maxx = max(tmp.maxx, u->val);
return tmp;
}
int maxAncestorDiff(TreeNode *root)
{
dfs(root);
return ans;
}
};
|