39 lines
1.2 KiB
C++
39 lines
1.2 KiB
C++
#include <limits>
|
|
|
|
/**
|
|
* 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 {
|
|
int maxAncestorDiff(TreeNode *node, int lower, int upper) const {
|
|
if (node == nullptr) {
|
|
return 0;
|
|
}
|
|
|
|
auto diff =
|
|
std::max(std::abs(node->val - lower), std::abs(node->val - upper));
|
|
auto [next_lower, next_upper] = std::make_tuple(
|
|
std::min(lower, node->val), std::max(upper, node->val));
|
|
|
|
diff =
|
|
std::max(diff, maxAncestorDiff(node->left, next_lower, next_upper));
|
|
diff = std::max(diff,
|
|
maxAncestorDiff(node->right, next_lower, next_upper));
|
|
|
|
return diff;
|
|
}
|
|
|
|
public:
|
|
int maxAncestorDiff(TreeNode *root) {
|
|
auto default_bound = root != nullptr ? root->val : 0;
|
|
return maxAncestorDiff(root, default_bound, default_bound);
|
|
}
|
|
};
|