Учитывая root
бинарного дерева, глубина каждого узла равна кратчайшему расстоянию до корня.
Возвратите наименьшее поддерево так, чтобы оно содержало все самые глубокие узлы в исходном дереве.
Узел называется самым глубоким, если он имеет наибольшую возможную глубину среди всех узлов во всем дереве.
Поддерево узла — это дерево, состоящее из этого узла и набора всех потомков этого узла.
Примечание. Этот вопрос аналогичен 1123: https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
Пример 1:
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.
Пример 2:
Input: root = [1] Output: [1] Explanation: The root is the deepest node in the tree.
Пример 3:
Input: root = [0,1,3,null,2] Output: [2] Explanation: The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.
Ограничения:
- Количество узлов в дереве будет в диапазоне
[1, 500]
. 0 <= Node.val <= 500
- Значения узлов в дереве уникальные.
Посетите ссылку ниже для решения с подробным объяснением