Клонировать двоичное дерево со случайными указателями

Question

Может кто-нибудь объяснить, как клонировать двоичное дерево со случайными указателями слева направо?каждый узел имеет следующую структуру.

struct node {  
    int key; 
    struct node *left,*right,*random;
} 

Это очень популярный вопрос для интервью, и я могу найти решение, основанное на хешировании (которое похоже на клонирование связанных списков).Я пытался понять решение, данное в Ссылка (подход 2), но не смог выяснить, что он хочет передать, читая код также.Я не ожидаю решения, основанного на хешировании, поскольку оно интуитивно понятно и довольно просто.Пожалуйста, объясните решение, основанное на модификации двоичного дерева и его клонировании.

Answer 1

Представленное решение основано на идее чередования обоих деревьев, исходного и его клона.

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

Для каждого узла B, который является правым дочерним элементом его родителя P (т. е. B == P->right), указатель на его клоновый узел cB копируется в клон его родителя.

       P                     P
      / \                   / \
     /   \                 /   \
    A     B               cP    B
   /       \             / \   / \
  /         \           /   \ /   \
 X           Z         A    cB     Z
                      /       \   /
                     cA        cZ
                    /
                   X
                  /
                 cX

Наконец, мы можем извлечь клонированное дерево, пройдя чередующееся дерево и отменив связькаждый второй узел на каждом «левом» пути (начиная с root->left) вместе с его «крайним правым» путем к потомкам и, рекурсивно, каждый второй «левый» потомок и так далее.

Что важно, каждый клонированный узел является прямым левым потомком своего исходного узла.Таким образом, в средней части алгоритма, после вставки клонированных узлов, но перед извлечением их, мы можем пройти по всему дереву, проходящему по исходным узлам, и всякий раз, когда мы находим указатель random, скажем A->random == Z, мы можем скопировать привязкув клоны, установив cA->random = cZ, который разрешает что-то вроде

A->left->random = A->random->left;

Это позволяет напрямую клонировать указатели random и не требует дополнительных хеш-карт (за счет чередования новых узлов в исходном дереве иизвлекая их позже).