Задача: 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 {
    public $val = 0;
    public $left = null;
    public $right = null;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    function recoverFromPreorder($S) {
        $stack = [];
        $i = 0;
        
        while ($i < strlen($S)) {
            $level = 0;
            while ($i < strlen($S) && $S[$i] == '-') {
                $level++;
                $i++;
            }
            
            $value = 0;
            while ($i < strlen($S) && is_numeric($S[$i])) {
                $value = $value * 10 + intval($S[$i]);
                $i++;
            }
            
            $node = new TreeNode($value);
            if ($level == count($stack)) {
                if (!empty($stack)) {
                    $stack[count($stack) - 1]->left = $node;
                }
            } else {
                while ($level != count($stack)) {
                    array_pop($stack);
                }
                $stack[count($stack) - 1]->right = $node;
            }
            array_push($stack, $node);
        }
        
        while (count($stack) > 1) {
            array_pop($stack);
        }
        
        return $stack[0];
    }
}

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