Code & Fun

第55天

今天的题目是Maximum Difference Between Node and Ancestor:

我们做一次后序遍历,维护一个子树的最大值和最小值,用当前节点的值与最大最小值求距离,并返回距离的最大值即可。

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
int maxAncestorDiff(TreeNode* root) {
if (root == nullptr) return -1;
int minVal, maxVal;
return maxAncestorDiff(root, minVal, maxVal);
}
int maxAncestorDiff1(TreeNode *root, int &minVal, int &maxVal) {
if (root == nullptr) return -1;
minVal = maxVal = root->val;

int d = -1, leftMin, leftMax, rightMin, rightMax;

if (root->left) {
int r = maxAncestorDiff(root->left, leftMin, leftMax);
d = max(r, max(abs(root->val - leftMin), abs(root->val - leftMax)));
minVal = min(minVal, leftMin);
maxVal = max(maxVal, leftMax);
}
if (root->right) {
int r = maxAncestorDiff(root->right, rightMin, rightMax);
d = max(d,max(r, max(abs(root->val - rightMax), abs(root->val - rightMin))));
minVal = min(minVal, rightMin);
maxVal = max(maxVal, rightMax);
}
if (!root->left && !root->right) return -1;
return d;
}

这样做可能有点过于复杂了,我们可以把后序遍历转成先序遍历来,同样也需要维护最大值和最小值,不过因为是先序遍历,所以比较简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxAncestorDiff(TreeNode* root) {
if (root == nullptr) return -1;
int minVal, maxVal;
minVal = maxVal = root->val;
return maxAncestorDiff(root, minVal, maxVal);
}

int maxAncestorDiff(TreeNode *root, int maxVal, int minVal) {
if (root == nullptr) return maxVal - minVal;
maxVal = max(maxVal, root->val);
minVal = min(minVal, root->val);
// cout << maxVal << " " << minVal << endl;
return max(maxAncestorDiff(root->left, maxVal, minVal),
maxAncestorDiff(root->right, maxVal, minVal));
}

本文首发于Code & Fun