Java 樹結構深拷貝：將子樹複製到另一節點下

需求場景

有一棵樹，需將某子樹完整複製到另一節點作為子節點，原樹保持不變，新節點數據獨立。

核心難點

• 避免淺拷貝導致節點對象共享
• 遞歸複製所有後代節點
• 斷開原父子關聯，建立新關聯

通用深拷貝模板

public class TreeNode {
    String data;
    List<TreeNode> children = new ArrayList<>();
    
    // 深拷貝構造函數
    public TreeNode(TreeNode source) {
        this.data = source.data; // String 不可變，直接賦值
        for (TreeNode child : source.children) {
            this.children.add(new TreeNode(child)); // 遞歸深拷貝
        }
    }
    
    // 靜態工廠方法
    public static TreeNode deepCopy(TreeNode root) {
        return root == null ? null : new TreeNode(root);
    }
}

複製到指定父節點

public void copySubtreeTo(TreeNode sourceSubtreeRoot, TreeNode targetParent) {
    if (sourceSubtreeRoot == null || targetParent == null) return;
    
    TreeNode newSubtree = TreeNode.deepCopy(sourceSubtreeRoot);
    targetParent.children.add(newSubtree);
}

若節點包含可變對象

public class TreeNode {
    private MutableData data; // 可變對象
    List<TreeNode> children = new ArrayList<>();
    
    public TreeNode(TreeNode source) {
        this.data = source.data.deepCopy(); // 必須深拷貝數據對象
        for (TreeNode child : source.children) {
            this.children.add(new TreeNode(child));
        }
    }
}

Cloneable 接口方式（不推薦）

雖可實現 clone()，但：

• 需實現 Cloneable 並處理 CloneNotSupportedException
• 默認淺拷貝，仍需手動深拷貝字段
• 破壞封裝性，現代 Java 推薦拷貝構造函數或工廠方法

測試驗證

TreeNode root = new TreeNode("A");
root.children.add(new TreeNode("B"));
root.children.add(new TreeNode("C"));
root.children.get(0).children.add(new TreeNode("D"));

TreeNode newParent = new TreeNode("X");
copySubtreeTo(root.children.get(0), newParent); // 複製 B 及其子樹到 X 下

// 驗證獨立性
newParent.children.get(0).data = "B_copy";
assert !root.children.get(0).data.equals("B_copy"); // 原樹未變