Сложность: 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 {
public:
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
unordered_map<TreeNode*, int> depth = {{nullptr, -1}};
dfs(root, nullptr, depth);
int maxDepth = max_element(depth.begin(), depth.end(), [](const auto& a, const auto& b) {
return a.second < b.second;
})->second;
return answer(root, depth, maxDepth);
}
private:
void dfs(TreeNode* node, TreeNode* parent, unordered_map<TreeNode*, int>& depth) {
if (node) {
depth[node] = depth[parent] + 1;
dfs(node->left, node, depth);
dfs(node->right, node, depth);
}
}
TreeNode* answer(TreeNode* node, unordered_map<TreeNode*, int>& depth, int maxDepth) {
if (!node || depth[node] == maxDepth) return node;
TreeNode* L = answer(node->left, depth, maxDepth);
TreeNode* R = answer(node->right, depth, maxDepth);
return L && R ? node : L ? L : R;
}
};Ставь 👍 и забирай 📚 Базу знаний