Code & Func

第55天

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

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

1
int maxAncestorDiff(TreeNode* root) {
2
    if (root == nullptr) return -1;
3
    int minVal, maxVal;
4
    return maxAncestorDiff(root, minVal, maxVal);
5
}
6
int maxAncestorDiff1(TreeNode *root, int &minVal, int &maxVal) {
7
    if (root == nullptr) return -1;
8
    minVal = maxVal = root->val;
9

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

12
    if (root->left) {
13
        int r = maxAncestorDiff(root->left, leftMin, leftMax);
14
        d = max(r, max(abs(root->val - leftMin), abs(root->val - leftMax)));
15
        minVal = min(minVal, leftMin);
11 collapsed lines
16
        maxVal = max(maxVal, leftMax);
17
    }
18
    if (root->right) {
19
        int r = maxAncestorDiff(root->right, rightMin, rightMax);
20
        d = max(d,max(r, max(abs(root->val - rightMax), abs(root->val - rightMin))));
21
        minVal = min(minVal, rightMin);
22
        maxVal = max(maxVal, rightMax);
23
    }
24
    if (!root->left && !root->right) return -1;
25
    return d;
26
}

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

1
int maxAncestorDiff(TreeNode* root) {
2
    if (root == nullptr) return -1;
3
    int minVal, maxVal;
4
    minVal = maxVal = root->val;
5
    return maxAncestorDiff(root, minVal, maxVal);
6
}
7

8
int maxAncestorDiff(TreeNode *root, int maxVal, int minVal) {
9
    if (root == nullptr) return maxVal - minVal;
10
    maxVal = max(maxVal, root->val);
11
    minVal = min(minVal, root->val);
12
    // cout << maxVal << " " << minVal << endl;
13
    return max(maxAncestorDiff(root->left, maxVal, minVal),
14
                maxAncestorDiff(root->right, maxVal, minVal));
15
}