Java二叉树克隆问题

Question

我有一个具有以下规范的 Java 二叉树，我需要克隆它。

public class Item {

    private final String value;
    public final Item left;
    public final Item right;

    ...

}

看似非常简单的任务让我感到困惑，因为克隆的树必须与原始树对象共享相同的单元格，而不是被复制。

但是，如果要将某个项目添加到原始树或克隆树中，则它不得传播到另一棵树。 IE。如果要将新项目添加到原始树中，则它不得出现在克隆树中，反之亦然。

此外，这需要在没有递归和任何循环构造的情况下完成。

所以我想知道是否有人能想到这样做，因为我不知道从哪里开始？

Answer 1

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);
        }

}