Задача: 919. Complete Binary Tree Inserter
Сложность: medium

Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, кроме, возможно, последнего, полностью заполнен, а все узлы расположены как можно дальше влево. Разработайте алгоритм вставки нового узла в полное двоичное дерево, сохраняя его полным после вставки.

Реализуйте класс CBTInserter: CBTInserter(TreeNode root) Инициализирует структуру данных корнем полного бинарного дерева. int insert(int v) Вставляет TreeNode в дерево со значением Node.val == val так, что дерево остается полным, и возвращает значение родителя вставленного TreeNode. TreeNode get_root() Возвращает корневой узел дерева.

Пример:

Input
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
Output
[null, 1, 2, [1, 2, 3, 4]]

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

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 CBTInserter {
    private $root;
    private $deque;

    function __construct($root) {
        $this->root = $root;
        $this->deque = [];
        $queue = [$root];
        while (!empty($queue)) {
            $node = array_shift($queue);
            if ($node->left === null || $node->right === null) {
                $this->deque[] = $node;
            }
            if ($node->left !== null) {
                $queue[] = $node->left;
            }
            if ($node->right !== null) {
                $queue[] = $node->right;
            }
        }
    }

    function insert($v) {
        $node = $this->deque[0];
        $newNode = new TreeNode($v);
        if ($node->left === null) {
            $node->left = $newNode;
        } else {
            $node->right = $newNode;
            array_shift($this->deque);
        }
        $this->deque[] = $newNode;
        return $node->val;
    }

    function get_root() {
        return $this->root;
    }
}

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