Задача: 865. Smallest Subtree with all the Deepest Nodes Сложность: 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); }; Ставь 👍 и забирай 📚 Базу знаний