Задача: 897. Increasing Order Search Tree
Сложность: easy

Задав корень дерева двоичного поиска, перестройте дерево по порядку так, чтобы самый левый узел дерева теперь был корнем дерева, а каждый узел не имел левого и только одного правого дочернего узла.

Пример:

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

👨‍💻 Алгоритм:

1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов.

2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null.

3⃣Вернуть новый корень дерева (первый элемент списка).

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function increasingBST($root) {
    $nodes = [];
    
    function inorder($node, &$nodes) {
        if ($node === null) return;
        inorder($node->left, $nodes);
        $nodes[] = $node;
        inorder($node->right, $nodes);
    }
    
    inorder($root, $nodes);
    
    for ($i = 0; $i < count($nodes) - 1; $i++) {
        $nodes[$i]->left = null;
        $nodes[$i]->right = $nodes[$i + 1];
    }
    
    $nodes[count($nodes) - 1]->left = null;
    $nodes[count($nodes) - 1]->right = null;
    return $nodes[0];
}

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