Задача: 1485. Clone Binary Tree With Random Pointer
Сложность: medium

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

Дерево представлено в том же формате ввода/вывода, что и обычные бинарные деревья, где каждый узел представлен в виде пары [val, random_index], где:
- val: целое число, представляющее Node.val
- random_index: индекс узла (во входных данных), на который указывает случайный указатель, или null, если он не указывает ни на один узел.

Вам будет дано дерево в классе Node, и вы должны вернуть клонированное дерево в классе NodeCopy. Класс NodeCopy является клоном класса Node с такими же атрибутами и конструкторами.

Пример:

Input: root = [[1,null],null,[4,3],[7,0]]
Output: [[1,null],null,[4,3],[7,0]]
Explanation: The original binary tree is [1,null,4,7].
The random pointer of node one is null, so it is represented as [1, null].
The random pointer of node 4 is node 7, so it is represented as [4, 3] where 3 is the index of node 7 in the array representing the tree.
The random pointer of node 7 is node 1, so it is represented as [7, 0] where 0 is the index of node 1 in the array representing the tree.

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

1⃣Глубокое копирование дерева:
Инициализируйте хэш-таблицу newOldPairs, которая сопоставляет узлы старого дерева с узлами нового дерева.
Создайте функцию deepCopy(root), которая принимает корень данного дерева и возвращает корень нового дерева. Эта функция создаёт новый узел с теми же значениями, что и корневой узел, и рекурсивно копирует левое и правое поддеревья. Затем она сохраняет пару старого и нового узлов в хэш-таблицу и возвращает новый корень.

2⃣Сопоставление случайных указателей:
Создайте функцию mapRandomPointers(oldNode), которая принимает корень старого дерева и рекурсивно сопоставляет случайные указатели нового дерева с соответствующими узлами старого дерева, используя хэш-таблицу newOldPairs.

3⃣Возвращение клонированного дерева:
Создайте глубокую копию дерева, используя функцию deepCopy(root), и сопоставьте все случайные указатели нового дерева с помощью функции mapRandomPointers(root). Верните новый корень.

😎 Решение:

class Node {
    public $val;
    public $left;
    public $right;
    public $random;

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

class NodeCopy {
    public $val;
    public $left;
    public $right;
    public $random;

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

class Solution {
    private $newOldPairs = [];

    private function deepCopy($root) {
        if ($root === null) {
            return null;
        }
        $newRoot = new NodeCopy($root->val);
        $newRoot->left = $this->deepCopy($root->left);
        $newRoot->right = $this->deepCopy($root->right);
        $this->newOldPairs[spl_object_id($root)] = $newRoot;
        return $newRoot;
    }

    private function mapRandomPointers($oldNode) {
        if ($oldNode === null) {
            return;
        }
        $newNode = $this->newOldPairs[spl_object_id($oldNode)];
        if ($newNode) {
            $newNode->random = $this->newOldPairs[spl_object_id($oldNode->random)] ?? null;
            $this->mapRandomPointers($oldNode->left);
            $this->mapRandomPointers($oldNode->right);
        }
    }

    public function copyRandomBinaryTree($root) {
        $newRoot = $this->deepCopy($root);
        $this->mapRandomPointers($root);
        return $newRoot;
    }
}

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