我有一个具有以下规范的 Java 二叉树,我需要克隆它。
public class Item {
private final String value;
public final Item left;
public final Item right;
...
}
看似非常简单的任务让我感到困惑,因为克隆的树必须与原始树对象共享相同的单元格,而不是被复制。
但是,如果要将某个项目添加到原始树或克隆树中,则它不得传播到另一棵树。 IE。如果要将新项目添加到原始树中,则它不得出现在克隆树中,反之亦然。
此外,这需要在没有递归和任何循环构造的情况下完成。
所以我想知道是否有人能想到这样做,因为我不知道从哪里开始?
最佳答案
Node cloneTree(Node root) {
Node n1 = new Node();
n1.value = root.value;
cloneTree(root, n1);
return n1;
}
void cloneTree(Node root, Node newNode) {
if (root == null) {
return;
}
if (root.leftNode != null) {
newNode.leftNode = new Node();
newNode.leftNode.value = root.leftNode.value;
cloneTree(root.leftNode, newNode.leftNode);
}
if (root.rightNode != null) {
newNode.rightNode = new Node();
newNode.rightNode.value = root.rightNode.value;
cloneTree(root.rightNode, newNode.rightNode);
}
}
关于Java二叉树克隆问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6043048/