Сложность: 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 {
var depth: [TreeNode: Int] = [:]
var maxDepth = -1
func subtreeWithAllDeepest(_ root: TreeNode?) -> TreeNode? {
depth[TreeNode()] = -1
dfs(root, nil)
for d in depth.values {
maxDepth = max(maxDepth, d)
}
return answer(root)
}
func dfs(_ node: TreeNode?, _ parent: TreeNode?) {
if let node = node {
depth[node] = depth[parent]! + 1
dfs(node.left, node)
dfs(node.right, node)
}
}
func answer(_ node: TreeNode?) -> TreeNode? {
if node == nil || depth[node] == maxDepth { return node }
let L = answer(node?.left)
let R = answer(node?.right)
if L != nil && R != nil { return node }
return L ?? R
}
}Ставь 👍 и забирай 📚 Базу знаний