Сложность: hard
Мы запускаем предварительный поиск в глубину (DFS) на корне двоичного дерева. На каждый узел в этом обходе мы выводим D тире (где D - глубина этого узла), а затем выводим значение этого узла.Если глубина узла равна D, то глубина его ближайшего потомка равна D + 1.Глубина корневого узла равна 0. Если у узла есть только один ребенок, то этот ребенок гарантированно является левым ребенком. Учитывая выходной обход этого обхода, восстановите дерево и верните его корень.
Пример:
Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]
👨💻 Алгоритм:
1⃣Разбор строки:
Пройдите по строке, чтобы определить уровни узлов и их значения. Используйте два счетчика: один для отслеживания текущего уровня (количество тире), второй для значения узла.
2⃣Создание узлов:
Создайте новые узлы на основе уровня и значения из строки. Для каждого нового узла найдите его родительский узел из стека и добавьте узел как левого или правого ребенка.
3⃣Построение дерева:
Используйте стек для отслеживания текущих узлов на каждом уровне глубины. Когда узел создан, добавьте его в стек. Если узел завершен, уберите его из стека.
😎 Решение:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def recoverFromPreorder(self, S: str) -> TreeNode:
stack = []
i = 0
while i < len(S):
level = 0
while i < len(S) and S[i] == '-':
level += 1
i += 1
value = 0
while i < len(S) and S[i].isdigit():
value = value * 10 + int(S[i])
i += 1
node = TreeNode(value)
if level == len(stack):
if stack:
stack[-1].left = node
else:
while level != len(stack):
stack.pop()
stack[-1].right = node
stack.append(node)
while len(stack) > 1:
stack.pop()
return stack[0]
Ставь 👍 и забирай 📚 Базу знаний