Problem
Given the root of a binary tree, find the maximum value v for which there exist 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.
Solution
Basically DFS. Pass the maximum and minimum value in the same path to leaf in recursive call. When reaching the leaf node, calculate the difference and compare all to get the maximum difference.
Implementation
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
/**
* 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 runner(TreeNode* root, int maxOnPath, int minOnPath) {
if (!root) return abs(maxOnPath - minOnPath);
maxOnPath = max(maxOnPath, root->val);
minOnPath = min(minOnPath, root->val);
int leftDiff = runner(root->left, maxOnPath, minOnPath);
int rightDiff = runner(root->right, maxOnPath, minOnPath);
return max(leftDiff, rightDiff);
}
int maxAncestorDiff(TreeNode* root) {
return runner(root, INT_MIN, INT_MAX);
}
};