使用随机指针克隆二叉树
Clone a Binary Tree with Random Pointers
谁能解释一下从左到右克隆随机指针二叉树的方法？每个节点都有以下结构。
struct node {
int key;
struct node *left,*right,*random;
}
这是一个非常受欢迎的面试问题，我能够找出基于散列的解决方案（类似于链表的克隆）。我试图理解 Link 中给出的解决方案（方法 2），但我也无法通过阅读代码来弄清楚它想要传达什么。
我不期望基于散列的解决方案，因为它直观且非常简单。请解释基于修改二叉树并克隆它的解决方案。
提出的解决方案基于交织 两棵树的想法，原始树及其克隆树。
对于原始树中的每个节点 A，都会创建其克隆 cA 并将其插入 A 的左侧 child。原来A的左child在树结构中向下移动了一层，变成了cA的左child。
对于每个节点B，这是其parentP（即B == P->right）的右child，指向其克隆的指针节点 cB 被复制到其 parent.
的克隆
P P
/ \ / \
/ \ / \
A B cP B
/ \ / \ / \
/ \ / \ / \
X Z A cB Z
/ \ /
cA cZ
/
X
/
cX
最后，我们可以通过遍历交错树并取消链接每个 'left' 路径（从 root->left 开始）上的每个其他节点及其 'rightmost' 后代路径来提取克隆树，并且，递归地，那些的每个其他 'left' 后代等等。
重要的是，每个克隆节点都是其原始节点的直接左 child。所以在算法的中间部分，在插入克隆节点之后提取它们之前，我们可以遍历整棵树在原始节点上行走，每当我们找到一个 random 指针时，说 A->random == Z，我们可以通过设置 cA->random = cZ 将绑定复制到克隆中，解析为
A->left->random = A->random->left;
这允许直接克隆 random 指针并且不需要额外的哈希映射（以将新节点交织到原始树中并在以后提取它们为代价）。
我觉得交错的方法可以稍微简化一下。
1) 对于原始树中的每个节点A，使用与A 相同的左右指针创建克隆cA。然后，将 As 左指针设置为 cA.
P P
/ \ /
/ \ /
A B cP
/ \ / \
/ \ / \
X Z A B
/ /
cA cB
/ \
X Z
/ /
cX cZ
2) 现在给定一个 node 和它的克隆（就是 node.left），克隆的随机指针是：node.random.left（如果 node.random 存在).
3) 最后二叉树可以解交错
我发现这种交错使得对代码的推理变得更加简单。
代码如下：
def clone_and_interleave(root):
if not root:
return
clone_and_interleave(root.left)
clone_and_interleave(root.right)
cloned_root = Node(root.data)
cloned_root.left, cloned_root.right = root.left, root.right
root.left = cloned_root
root.right = None # This isn't necessary, but doesn't hurt either.
def set_randoms(root):
if not root:
return
cloned_root = root.left
set_randoms(cloned_root.left)
set_randoms(cloned_root.right)
cloned_root.random = root.random.left if root.random else None
def unterleave(root):
if not root:
return (None, None)
cloned_root = root.left
cloned_root.left, root.left = unterleave(cloned_root.left)
cloned_root.right, root.right = unterleave(cloned_root.right)
return (cloned_root, root)
def cloneTree(root):
clone_and_interleave(root)
set_randoms(root)
cloned_root, root = unterleave(root)
return cloned_root
那些面试问题中使用的术语非常糟糕。这是一个不知情的 kuckledgragger 在某处称该指针为“随机”指针的情况，每个人都点头并接受它，就好像这是来自象牙塔的一些 CS 咒语。唉，这纯粹是疯了。
要么你拥有的是一棵树，要么不是。树是一个无环有向图，最多有一条边指向任何节点，添加额外的指针不能改变它——指针指向的东西必须保留这个 属性.
但是当节点有一个可以指向任何其他节点的指针时，它就不是一棵树。你得到了一个合适的有向图，里面有循环，此时把它看成一棵树是很愚蠢的。它不是一棵树。它只是您要克隆的通用有向边图。所以任何相关的有向图克隆技术都可以工作，但是坚持使用术语“树”和“随机指针”掩盖了这个简单的事实，并且把事情搞得一团糟。
这个问题说明出这个问题的人没有资格做这样的采访。这些东西在任何体面的介绍性数据结构教科书中都有介绍，因此您认为它不应该呈现出一些天文数字的艰巨努力，只是以直接的方式阐明您的需求。让面试者在获得这份工作后与无法表达自己的用户打交道——数据结构面试既不是那个地方，也不是那个时间。它散发着愚蠢和粗心的味道，并留下永久的不良回味。这可能是另一个愚蠢的事情，最终出现在一些“面试题库”中，因为一个可怜的人曾经被一个粗心的白痴问过，现在每个人都把它当作福音。这又是盲人带领盲人和无能为力的情况。
复制任意图是一个很好解决的问题，在所有情况下，您都需要以某种方式保留遍历的状态。无论是通过在原始图中插入节点来标记进度——我们可以称之为侵入式标记——还是通过向正在进行的副本添加数据并在完成后删除它，或者通过使用辅助结构（如散列），或者通过做重复遍历来检查你在别处复制了那个节点 - 是次要的，因为目的总是相同的：保留相同的状态信息，只是以各种方式对其进行编码，权衡速度和内存使用（如总是）。
想到这个问题的时候，你需要告诉自己需要什么样的状态才能完成拷贝，然后抽象出来，用这个抽象接口实现拷贝。然后你可以通过几种方式实现它，但此时复制本身并没有混淆，因为你看的是这个简单的抽象 state-preserving 接口而不是复制过程。
在现实生活中，任何特定实现的选择在很大程度上取决于要复制的数据的数量和结构，以及您对这一切的控制程度。如果您是控制节点结构的人，那么您通常会发现它们有一些可以用来存储一些状态信息的填充。或者你会发现为节点分配的内存块实际上比请求的要大：malloc 通常最终会提供比要求的更大的块，并且所有合理的平台都有 API 可以让你检索实际大小块，从而检查是否有一些剩余的 space 只是乞求使用。这些 API 并不总是很快，所以当然要小心。但是您知道这是怎么回事：这种优化需要基准测试和由应用程序需求驱动的明确需求。否则，使用任何不太可能出现错误的东西——最好是一个 C 库，它提供您可以立即使用的数据结构。如果你需要一个循环图，有一些库可以做到这一点——首先使用它们。
但是孩子，我讨厌指针的那个愚蠢的“随机”名称吗？谁想出这些废话，为什么他们污染了这么多人的思想？没有什么随机的。而不是树的树就不是树。我会在一瞬间让面试官失望......
谁能解释一下从左到右克隆随机指针二叉树的方法？每个节点都有以下结构。
struct node {
int key;
struct node *left,*right,*random;
}
这是一个非常受欢迎的面试问题，我能够找出基于散列的解决方案（类似于链表的克隆）。我试图理解 Link 中给出的解决方案（方法 2），但我也无法通过阅读代码来弄清楚它想要传达什么。 我不期望基于散列的解决方案，因为它直观且非常简单。请解释基于修改二叉树并克隆它的解决方案。
提出的解决方案基于交织 两棵树的想法，原始树及其克隆树。
对于原始树中的每个节点 A，都会创建其克隆 cA 并将其插入 A 的左侧 child。原来A的左child在树结构中向下移动了一层，变成了cA的左child。
对于每个节点B，这是其parentP（即B == P->right）的右child，指向其克隆的指针节点 cB 被复制到其 parent.
P P
/ \ / \
/ \ / \
A B cP B
/ \ / \ / \
/ \ / \ / \
X Z A cB Z
/ \ /
cA cZ
/
X
/
cX
最后，我们可以通过遍历交错树并取消链接每个 'left' 路径（从 root->left 开始）上的每个其他节点及其 'rightmost' 后代路径来提取克隆树，并且，递归地，那些的每个其他 'left' 后代等等。
重要的是，每个克隆节点都是其原始节点的直接左 child。所以在算法的中间部分，在插入克隆节点之后提取它们之前，我们可以遍历整棵树在原始节点上行走，每当我们找到一个 random 指针时，说 A->random == Z，我们可以通过设置 cA->random = cZ 将绑定复制到克隆中，解析为
A->left->random = A->random->left;
这允许直接克隆 random 指针并且不需要额外的哈希映射（以将新节点交织到原始树中并在以后提取它们为代价）。
我觉得交错的方法可以稍微简化一下。
1) 对于原始树中的每个节点A，使用与A 相同的左右指针创建克隆cA。然后，将 As 左指针设置为 cA.
P P
/ \ /
/ \ /
A B cP
/ \ / \
/ \ / \
X Z A B
/ /
cA cB
/ \
X Z
/ /
cX cZ
2) 现在给定一个 node 和它的克隆（就是 node.left），克隆的随机指针是：node.random.left（如果 node.random 存在).
3) 最后二叉树可以解交错
我发现这种交错使得对代码的推理变得更加简单。
代码如下：
def clone_and_interleave(root):
if not root:
return
clone_and_interleave(root.left)
clone_and_interleave(root.right)
cloned_root = Node(root.data)
cloned_root.left, cloned_root.right = root.left, root.right
root.left = cloned_root
root.right = None # This isn't necessary, but doesn't hurt either.
def set_randoms(root):
if not root:
return
cloned_root = root.left
set_randoms(cloned_root.left)
set_randoms(cloned_root.right)
cloned_root.random = root.random.left if root.random else None
def unterleave(root):
if not root:
return (None, None)
cloned_root = root.left
cloned_root.left, root.left = unterleave(cloned_root.left)
cloned_root.right, root.right = unterleave(cloned_root.right)
return (cloned_root, root)
def cloneTree(root):
clone_and_interleave(root)
set_randoms(root)
cloned_root, root = unterleave(root)
return cloned_root
那些面试问题中使用的术语非常糟糕。这是一个不知情的 kuckledgragger 在某处称该指针为“随机”指针的情况，每个人都点头并接受它，就好像这是来自象牙塔的一些 CS 咒语。唉，这纯粹是疯了。
要么你拥有的是一棵树，要么不是。树是一个无环有向图，最多有一条边指向任何节点，添加额外的指针不能改变它——指针指向的东西必须保留这个 属性.
但是当节点有一个可以指向任何其他节点的指针时，它就不是一棵树。你得到了一个合适的有向图，里面有循环，此时把它看成一棵树是很愚蠢的。它不是一棵树。它只是您要克隆的通用有向边图。所以任何相关的有向图克隆技术都可以工作，但是坚持使用术语“树”和“随机指针”掩盖了这个简单的事实，并且把事情搞得一团糟。
这个问题说明出这个问题的人没有资格做这样的采访。这些东西在任何体面的介绍性数据结构教科书中都有介绍，因此您认为它不应该呈现出一些天文数字的艰巨努力，只是以直接的方式阐明您的需求。让面试者在获得这份工作后与无法表达自己的用户打交道——数据结构面试既不是那个地方，也不是那个时间。它散发着愚蠢和粗心的味道，并留下永久的不良回味。这可能是另一个愚蠢的事情，最终出现在一些“面试题库”中，因为一个可怜的人曾经被一个粗心的白痴问过，现在每个人都把它当作福音。这又是盲人带领盲人和无能为力的情况。
复制任意图是一个很好解决的问题，在所有情况下，您都需要以某种方式保留遍历的状态。无论是通过在原始图中插入节点来标记进度——我们可以称之为侵入式标记——还是通过向正在进行的副本添加数据并在完成后删除它，或者通过使用辅助结构（如散列），或者通过做重复遍历来检查你在别处复制了那个节点 - 是次要的，因为目的总是相同的：保留相同的状态信息，只是以各种方式对其进行编码，权衡速度和内存使用（如总是）。
想到这个问题的时候，你需要告诉自己需要什么样的状态才能完成拷贝，然后抽象出来，用这个抽象接口实现拷贝。然后你可以通过几种方式实现它，但此时复制本身并没有混淆，因为你看的是这个简单的抽象 state-preserving 接口而不是复制过程。
在现实生活中，任何特定实现的选择在很大程度上取决于要复制的数据的数量和结构，以及您对这一切的控制程度。如果您是控制节点结构的人，那么您通常会发现它们有一些可以用来存储一些状态信息的填充。或者你会发现为节点分配的内存块实际上比请求的要大：malloc 通常最终会提供比要求的更大的块，并且所有合理的平台都有 API 可以让你检索实际大小块，从而检查是否有一些剩余的 space 只是乞求使用。这些 API 并不总是很快，所以当然要小心。但是您知道这是怎么回事：这种优化需要基准测试和由应用程序需求驱动的明确需求。否则，使用任何不太可能出现错误的东西——最好是一个 C 库，它提供您可以立即使用的数据结构。如果你需要一个循环图，有一些库可以做到这一点——首先使用它们。
但是孩子，我讨厌指针的那个愚蠢的“随机”名称吗？谁想出这些废话，为什么他们污染了这么多人的思想？没有什么随机的。而不是树的树就不是树。我会在一瞬间让面试官失望......