Задача: 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<TreeNode>();
        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();
    }
}

Ставь 👍 и забирай 📚 Базу знаний