Задача: 623. Add One Row to Tree
Сложность: medium

Учитывая корень бинарного дерева и два целых числа val и depth, добавьте ряд узлов со значением val на заданную глубину depth. Обратите внимание, что корневой узел находится на глубине 1. Правило добавления таково: учитывая целое число depth, для каждого ненулевого узла дерева cur на глубине depth - 1 создайте два узла дерева со значением val в качестве левого поддерева корня cur и правого поддерева корня.
Оригинальное левое поддерево cur должно быть левым поддеревом нового корня левого поддерева. Оригинальное правое поддерево cur должно быть правым поддеревом нового корня правого поддерева. Если глубина == 1, то есть глубина - 1 вообще не существует, создайте узел дерева со значением val как новый корень всего оригинального дерева, а оригинальное дерево - левое поддерево нового корня.

Пример:

Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]

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

1⃣Если depth равна 1, создайте новый корень со значением val и сделайте текущий корень левым поддеревом нового корня.

2⃣Используйте обход в ширину (BFS) для поиска всех узлов на глубине depth - 1.

3⃣Для каждого узла на глубине depth - 1, вставьте новые узлы со значением val в качестве левого и правого поддеревьев, сохраняя исходные поддеревья.

😎 Решение:

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 addOneRow($root, $val, $depth) {
    if ($depth == 1) {
        return new TreeNode($val, $root);
    }
    
    $queue = [$root];
    $currentDepth = 1;
    
    while (!empty($queue)) {
        if ($currentDepth == $depth - 1) {
            foreach ($queue as $node) {
                $node->left = new TreeNode($val, $node->left);
                $node->right = new TreeNode($val, null, $node->right);
            }
            break;
        }
        $currentDepth++;
        $nextQueue = [];
        foreach ($queue as $node) {
            if ($node->left !== null) {
                $nextQueue[] = $node->left;
            }
            if ($node->right !== null) {
                $nextQueue[] = $node->right;
            }
        }
        $queue = $nextQueue;
    }
    
    return $root;
}

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