使用随机指针克隆二叉树

Question

谁能解释一下从左到右用随机指针克隆二叉树的方法？每个节点都有以下结构。

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

这是一个非常受欢迎的面试问题，我能够找出基于散列的解决方案(类似于链表的克隆)。我试图理解 Link 中给出的解决方案(方法 2)但我也无法通过阅读代码来弄清楚它想要传达什么。我不期望基于散列的解决方案，因为它直观且非常简单。请解释基于修改二叉树并克隆它的解决方案。

Answer 1

所提出的解决方案基于交织两棵树的想法，即原始树及其克隆树。

对于原始树中的每个节点 A，都会创建其克隆 cA 并将其作为 A 的左子节点插入。 A 的原始左 child 在树结构中向下移动一级，成为 cA 的左 child 。

对于每个节点 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 将绑定(bind)复制到克隆中，解析为类似于

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

这允许直接克隆随机指针并且不需要额外的 HashMap (以将新节点交织到原始树中并在以后提取它们为代价)。