leetcode 1026 - Maximum Difference Between Node and Ancestor

https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/

Given the root of a binary tree, find the maximum value V for which there exists different nodes A and B where V = |A.val - B.val| and A is an ancestor of B.

(A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.)

Example 1:

[]

Input: [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation:
We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

Note:

The number of nodes in the tree is between 2 and 5000.
Each node will have value between 0 and 100000.

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
* Definition for a binary tree node.
* 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 maxDiff;

int maxAncestorDiff(TreeNode* root) {
maxDiff = INT_MIN;

minMaxNode(root);

return maxDiff;
}

vector<TreeNode *> minMaxNode(TreeNode *root) {
if (!root)
return {NULL, NULL};

vector<TreeNode *> left = minMaxNode(root->left);
vector<TreeNode *> right = minMaxNode(root->right);

vector<TreeNode *> min_max = {root, root};

if (left[0]) {
maxDiff = max(maxDiff, abs(root->val - left[0]->val));
maxDiff = max(maxDiff, abs(root->val - left[1]->val));

if (left[0]->val < min_max[0]->val)
min_max[0] = left[0];
if (left[1]->val > min_max[1]->val)
min_max[1] = left[1];
}

if (right[0]) {
maxDiff = max(maxDiff, abs(root->val - right[0]->val));
maxDiff = max(maxDiff, abs(root->val - right[1]->val));

if (right[0]->val < min_max[0]->val)
min_max[0] = right[0];
if (right[1]->val > min_max[1]->val)
min_max[1] = right[1];
}

return min_max;
}
};