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
|
// 1026. Maximum Difference Between Node and Ancestor
#include "leetcode.h"
/*
* 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 ancesotr of 'b'. a node 'a' is an ancesotr of 'b' if either any child if
* 'a' is equal to 'b' or any child 'a' is an ancestor of 'b'.
*/
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int helper(struct TreeNode *node, int min_seen, int max_seen) {
int leftdiff, rightdiff;
if (!(node->val < min_seen || node->val > max_seen))
;
else {
if (node->val > max_seen)
max_seen = node->val;
else
min_seen = node->val;
}
int diff = max_seen - min_seen;
if (node->left == NULL && node->right == NULL)
return diff;
else if (!(node->left != NULL && node->right != NULL)) {
if (node->left == NULL) {
leftdiff = 0;
rightdiff = helper(node->right, min_seen, max_seen);
return (rightdiff > diff ? rightdiff : diff);
} else {
rightdiff = 0;
leftdiff = helper(node->left, min_seen, max_seen);
return (leftdiff > diff ? leftdiff : diff);
}
} else {
leftdiff = helper(node->left, min_seen, max_seen);
rightdiff = helper(node->right, min_seen, max_seen);
return leftdiff > rightdiff ? leftdiff : rightdiff;
}
}
int maxAncestorDiff(struct TreeNode *root) {
return !root ? 0 : helper(root, root->val, root->val);
}
|