🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1028. Recover a Tree From Preorder Traversal
Сложность: 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⃣Построение дерева:
Используйте стек для отслеживания текущих узлов на каждом уровне глубины. Когда узел создан, добавьте его в стек. Если узел завершен, уберите его из стека.
😎 Решение:
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode RecoverFromPreorder(string S) {
var stack = new Stack();
for (int i = 0; i < S.Length;) {
int level = 0;
while (i < S.Length && S[i] == '-') {
level++;
i++;
}
int value = 0;
while (i < S.Length && char.IsDigit(S[i])) {
value = value * 10 + (S[i] - '0');
i++;
}
TreeNode node = new TreeNode(value);
if (level == stack.Count) {
if (stack.Count > 0) {
stack.Peek().left = node;
}
} else {
while (level != stack.Count) {
stack.Pop();
}
stack.Peek().right = node;
}
stack.Push(node);
}
while (stack.Count > 1) {
stack.Pop();
}
return stack.Peek();
}
}
Ставь 👍 и забирай 📚 Базу знаний