Сложность: 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) возвращает поддерево, которое содержит все самые глубокие узлы всего дерева, а не только рассматриваемого поддерева.
😎 Решение:
var subtreeWithAllDeepest = function(root) {
const depth = new Map([[null, -1]]);
const dfs = (node, parent) => {
if (node) {
depth.set(node, depth.get(parent) + 1);
dfs(node.left, node);
dfs(node.right, node);
}
};
dfs(root, null);
const maxDepth = Math.max(...depth.values());
const answer = (node) => {
if (!node || depth.get(node) === maxDepth) return node;
const L = answer(node.left);
const R = answer(node.right);
return L && R ? node : L || R;
};
return answer(root);
};Ставь 👍 и забирай 📚 Базу знаний