Задача: 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⃣Построение дерева:
Используйте стек для отслеживания текущих узлов на каждом уровне глубины. Когда узел создан, добавьте его в стек. Если узел завершен, уберите его из стека.

😎 Решение:

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    recoverFromPreorder(S) {
        const stack = [];
        let i = 0;
        
        while (i < S.length) {
            let level = 0;
            while (i < S.length && S[i] === '-') {
                level++;
                i++;
            }
            
            let value = 0;
            while (i < S.length && !isNaN(S[i])) {
                value = value * 10 + parseInt(S[i], 10);
                i++;
            }
            
            const node = new TreeNode(value);
            if (level === stack.length) {
                if (stack.length > 0) {
                    stack[stack.length - 1].left = node;
                }
            } else {
                while (level !== stack.length) {
                    stack.pop();
                }
                stack[stack.length - 1].right = node;
            }
            stack.push(node);
        }
        
        while (stack.length > 1) {
            stack.pop();
        }
        
        return stack[0];
    }
}

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