Сложность: medium
Дан корень бинарного дерева, глубина каждого узла — это кратчайшее расстояние до корня.
Верните наименьшее поддерево, которое содержит все самые глубокие узлы в исходном дереве.
Узел называется самым глубоким, если у него наибольшая возможная глубина среди всех узлов в дереве.
Поддерево узла — это дерево, состоящее из этого узла и всех его потомков.
Пример:
Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.
👨💻 Алгоритм:
1⃣В первой фазе используем поиск в глубину (DFS), чтобы аннотировать узлы. Каждый узел будет хранить информацию о своей глубине и о самой большой глубине среди его потомков.
2⃣Во второй фазе также используем DFS для функции answer(node), которая возвращает наименьшее поддерево, содержащее все самые глубокие узлы. Функция сравнивает глубины левых и правых поддеревьев узла для определения наименьшего поддерева.
3⃣Функция answer(node) возвращает поддерево, которое содержит все самые глубокие узлы всего дерева, а не только рассматриваемого поддерева.
😎 Решение:
class Solution {
private $depth = [];
private $maxDepth = -1;
function subtreeWithAllDeepest($root) {
$this->depth[null] = -1;
$this->dfs($root, null);
$this->maxDepth = max($this->depth);
return $this->answer($root);
}
private function dfs($node, $parent) {
if ($node !== null) {
$this->depth[$node->val] = $this->depth[$parent->val] + 1;
$this->dfs($node->left, $node);
$this->dfs($node->right, $node);
}
}
private function answer($node) {
if ($node === null || $this->depth[$node->val] == $this->maxDepth) return $node;
$L = $this->answer($node->left);
$R = $this->answer($node->right);
if ($L !== null && $R !== null) return $node;
return $L !== null ? $L : $R;
}
}Ставь 👍 и забирай 📚 Базу знаний