Сложность: 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 {
Map<TreeNode, Integer> depth;
int maxDepth;
public TreeNode subtreeWithAllDeepest(TreeNode root) {
depth = new HashMap<>();
depth.put(null, -1);
dfs(root, null);
maxDepth = depth.values().stream().max(Integer::compare).orElse(-1);
return answer(root);
}
private void dfs(TreeNode node, TreeNode parent) {
if (node != null) {
depth.put(node, depth.get(parent) + 1);
dfs(node.left, node);
dfs(node.right, node);
}
}
private TreeNode answer(TreeNode node) {
if (node == null || depth.get(node) == maxDepth) return node;
TreeNode L = answer(node.left), R = answer(node.right);
if (L != null && R != null) return node;
return L != null ? L : R;
}
}Ставь 👍 и забирай 📚 Базу знаний