Сложность: 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⃣Рекурсивный вызов для детей:
Рекурсивно вызывайте функцию для левого и правого поддерева, передавая обновленные минимальное и максимальное значения.
😎 Решение:
class TreeNode {
public $val = 0;
public $left = null;
public $right = null;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
class Solution {
function maxAncestorDiff($root) {
return $this->dfs($root, $root->val, $root->val);
}
private function dfs($node, $minVal, $maxVal) {
if ($node === null) return $maxVal - $minVal;
$minVal = min($minVal, $node->val);
$maxVal = max($maxVal, $node->val);
$left = $this->dfs($node->left, $minVal, $maxVal);
$right = $this->dfs($node->right, $minVal, $maxVal);
return max($left, $right);
}
}Ставь 👍 и забирай 📚 Базу знаний