LeetCode 1490. 克隆 N 叉树
题目描述
题意分析
给定一棵 N 叉树，创建一棵结构完全相同的新树：对应节点值一致，每个节点的孩子数量和排列顺序也一致。
这是深拷贝，副本的所有节点及孩子容器都必须独立于原树。只复制根的值、列表或指针都不够；修改任一副本节点不应影响原树。空树的副本仍为空。
解法：深度优先递归克隆
核心思路
[!blue]
定义递归函数返回“当前节点为根的整棵子树的独立副本”。如果当前节点为空，直接返回空；否则先创建一个同值的新节点，并为它建立新的孩子容器。
按原顺序访问每个孩子，递归得到该孩子整棵子树的副本，再将返回的新根加入新容器。不能把原孩子直接加入，因为容器独立并不代表里面的节点也独立。
叶子没有孩子，创建同值新节点后即可完成。假设各个孩子的递归结果已经保留结构与顺序、且没有共享原节点，将它们接到当前新节点后，整棵子树也满足同样条件。这个从叶到根的递归关系保证最终得到完整深拷贝。
输入是树，每个非根节点只有一个父节点，没有环或跨分支共享引用，所以每个原节点只会沿唯一父子路径被复制一次，不需要像克隆图那样建立访问映射。
解题步骤
- 当前根为空时返回空。
- 创建值与当前根相同的新节点，并初始化新的孩子容器。
- 按原孩子列表顺序，递归克隆每棵孩子子树。
- 将返回的副本根依次放入新容器，返回当前新节点。
代码实现
class Solution {
// N 叉树没有随机指针和回边，从根递归复制每个子树即可，不需要哈希表记录已访问节点。
public Node cloneTree(Node root) {
if (root == null) {
return null;
}
Node copy = new Node(root.val);
// 新容器只放克隆后的孩子，不复用原孩子对象。
copy.children = new ArrayList<>();
for (Node child : root.children) {
// 按原孩子顺序递归复制，保持结构和顺序。
copy.children.add(cloneTree(child));
}
return copy;
}
}
// 返回保持值与孩子顺序的独立子树副本，不共享源节点。
func cloneTree(root *Node) *Node {
// N 叉树没有随机指针和回边，从根递归复制每个子树即可，不需要哈希表记录已访问节点。
if root == nil {
return nil
}
// 为当前节点创建独立对象与孩子容器。
node := &Node{
Val: root.Val,
Children: make([]*Node, 0, len(root.Children)),
}
for _, child := range root.Children {
// 按原孩子顺序递归复制，保持结构和顺序。
node.Children = append(node.Children, cloneTree(child))
}
return node
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点创建一次，每条父子连接处理一次。
- 空间复杂度：辅助递归栈为 $O(h)$，其中 $h$ 是树高；深拷贝输出本身需要 $O(n)$。
关键点总结
[!green]
- 递归返回完整子树副本，父节点只负责把这些新子树按顺序接起来。
- 节点对象和孩子容器都要新建，所有连接都指向副本。
- 树的唯一父子路径保证不会重复复制，无需额外映射。
易错点总结
[!yellow]
- 直接返回原节点只多了一个引用，没有复制数据结构。
- 创建新列表却放入原孩子，仍会共享整棵孩子子树。
- 只克隆第一层孩子而不继续递归，会遗漏更深层节点。
- 随意改变孩子加入顺序，会改变题目要求保留的有序结构。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 133. 克隆图 | 中等 | 图克隆需要映射处理共享与环，本题是纯N叉树时可直接递归复制孩子列表。 |
| 1485. 克隆含随机指针的二叉树 | 中等 | 原题还含随机指针，需要额外引用映射，本题只有正常父子层级。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！