c - 使用随机指针克隆二叉树

Question

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

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

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

标签： calgorithmrecursiondata-structuresbinary-tree

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