谁能解释一下从左到右用随机指针克隆二叉树的方法?每个节点都有以下结构。
struct node {
int key;
struct node *left,*right,*random;
}
这是一个非常受欢迎的面试问题,我能够找出基于散列的解决方案(类似于链表的克隆)。我试图理解 Link 中给出的解决方案(方法 2)但我也无法通过阅读代码来弄清楚它想要传达什么。 我不期望基于散列的解决方案,因为它直观且非常简单。请解释基于修改二叉树并克隆它的解决方案。
最佳答案
所提出的解决方案基于交织两棵树的想法,即原始树及其克隆树。
对于原始树中的每个节点 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 (以将新节点交织到原始树中并在以后提取它们为代价)。
关于使用随机指针克隆二叉树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50796420/