🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1026. Maximum Difference Between Node and Ancestor
Сложность: 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⃣Рекурсивный вызов для детей:
Рекурсивно вызывайте функцию для левого и правого поддерева, передавая обновленные минимальное и максимальное значения.
😎 Решение:
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public int MaxAncestorDiff(TreeNode root) {
return Dfs(root, root.val, root.val);
}
private int Dfs(TreeNode node, int minVal, int maxVal) {
if (node == null) return maxVal - minVal;
minVal = Math.Min(minVal, node.val);
maxVal = Math.Max(maxVal, node.val);
int left = Dfs(node.left, minVal, maxVal);
int right = Dfs(node.right, minVal, maxVal);
return Math.Max(left, right);
}
}
Ставь 👍 и забирай 📚 Базу знаний