克隆带有随机指针的二叉树

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直接克隆指针并且不需要额外的哈希映射（代价是将新节点交错到原始树中并稍后提取它们）。