Сложность: medium
Учитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b.
Пример:
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
👨💻 Алгоритм:
1⃣Рекурсивный обход дерева:
Используйте рекурсивную функцию для обхода дерева. Передавайте минимальное и максимальное значения, встреченные на пути от корня к текущему узлу.
2⃣Обновление максимальной разницы:
При посещении каждого узла обновляйте минимальное и максимальное значения. Вычисляйте разницу между текущим значением узла и минимальным и максимальным значениями на пути. Обновляйте максимальную разницу, если текущая разница больше.
3⃣Рекурсивный вызов для детей:
Рекурсивно вызывайте функцию для левого и правого поддерева, передавая обновленные минимальное и максимальное значения.
😎 Решение:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxAncestorDiff(TreeNode* root) {
return dfs(root, root->val, root->val);
}
private:
int dfs(TreeNode* node, int min_val, int max_val) {
if (!node) return max_val - min_val;
min_val = min(min_val, node->val);
max_val = max(max_val, node->val);
int left = dfs(node->left, min_val, max_val);
int right = dfs(node->right, min_val, max_val);
return max(left, right);
}
};Ставь 👍 и забирай 📚 Базу знаний