LeetCode 1490. 克隆 N 叉树

2023-09-12 HGNULB 约 7 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 1490. 克隆 N 叉树

题意分析

给一棵 N 叉树的根，返回一棵和它「结构与取值完全一致」的新树。判定标准是深拷贝：新树里的每一个节点、每一个孩子列表都必须是新建的对象，不能有任何一处仍然指向原树。

要求里最容易被忽略的是「孩子列表本身也要新建」。就算节点对象是新的，如果直接把原节点的 children 引用赋过去，两棵树就共享了同一个列表，往新树里加删孩子会污染原树，这依然不算深拷贝。

孩子是有序的，克隆后的顺序必须和原来逐位对应，不能因为用了集合或者反向遍历而打乱。

结构上这是一棵真正的树：没有环、没有跨层回边、每个节点恰好有一个父亲，所以任何节点都不会被两条不同的路径访问到。这一条决定了本题不需要记录访问状态。边界情形是空树，直接返回空。

解法：深度优先递归克隆

核心思路

先想最笨的办法：层序遍历原树，为每个节点造一个副本，再用一张哈希表把「原节点 → 新节点」记下来，第二趟按表把父子关系接上。这个流程完全正确，也是克隆图那类题的标准套路，但对树来说它多做了一件事——维护映射表。

映射表存在的意义是处理「同一个节点被多次到达」。在一般的图里，两条路径可能指向同一节点，第二次遇到时必须复用第一次造好的副本，否则会造出重复对象甚至无限递归。而树的定义排除了这种可能：从根出发，到每个节点的路径唯一，每个节点恰好被访问一次。于是映射表永远不会命中已有条目，它的存在纯属浪费。

去掉映射表之后，问题就退化成一个干净的递归定义：克隆以 root 为根的子树，等于新建一个值相同的节点，再把 root 的每个孩子的克隆结果按原顺序挂到它下面。

这里的不变量是：cloneTree(node) 返回的子树与以 node 为根的原子树同构、同值，且其中不含任何原树对象。递归出口 root == null 返回 null 自然满足它；递归步骤中新节点是 new 出来的、孩子列表是新建的、每个孩子由归纳假设保证也是干净的，于是不变量逐层向上成立，根节点返回时整棵树都是新的。

解题步骤

root == null 时直接返回 null。这既是递归的终止条件，也顺带处理了整棵树为空的输入，不用在调用处额外判断。

用 root 的值新建一个节点 copy。必须走构造函数造新对象，任何形式的「拿到原节点再改改」都会留下共享。

给 copy 挂一个全新的空孩子列表。这一步单独强调，是因为它是深拷贝最容易漏掉的地方：节点新建了但列表复用，两棵树依然纠缠在一起。

按下标顺序遍历 root 的孩子，对每个孩子递归调用自身，把返回的子树根依次追加进 copy 的孩子列表。顺序遍历加顺序追加，孩子的次序就自动保持了。

返回 copy。对调用方而言它就是「这棵子树的克隆根」，递归靠这个返回值把子树逐层拼接起来。

以 root = [1,null,3,2,4,null,5,6] 走一遍（根 1 有三个孩子 3、2、4，节点 3 又有两个孩子 5、6）：调用 cloneTree(1)，非空，新建节点 $1'$ 和空列表，开始遍历孩子。第一个孩子是 3，进入 cloneTree(3)，新建 $3'$ 和空列表；它的第一个孩子 5 递归下去，5 没有孩子，循环体一次都不执行，直接返回带空列表的 $5'$，追加到 $3'$ 下；第二个孩子 6 同理返回 $6'$ 并追加。cloneTree(3) 返回孩子列表为 $[5', 6']$ 的 $3'$，追加到 $1'$ 下。回到根的循环，第二个孩子 2 是叶子，返回 $2'$ 并追加；第三个孩子 4 也是叶子，返回 $4'$ 并追加。最终 cloneTree(1) 返回的 $1'$ 孩子列表是 $[3', 2', 4']$，与原树的 $[3, 2, 4]$ 顺序一致，而 $3'$ 下挂着 $[5', 6']$。整个过程一共调用六次函数，恰好等于节点数，每个原节点被访问一次。

代码实现

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)$，$n$ 为节点总数。每个原节点触发一次函数调用，调用内部只做常数次新建加一次对孩子列表的线性遍历，而所有节点的孩子数之和恰好是 $n - 1$。

空间复杂度：$O(h)$ 的递归栈加 $O(n)$ 的输出，$h$ 是树高。链状退化时 $h = n$，栈深与节点数同阶；返回的新树本身属于必要产出，通常不计入额外空间。

关键点总结

深拷贝的判定标准是「新结构不持有任何原对象的引用」，节点要新建，容器也要新建。只换节点不换列表是最典型的假深拷贝。

树和图的克隆差别只在一处：图需要「原节点 → 新节点」的哈希表来复用已建副本并防止环上无限递归，树因为访问路径唯一所以不需要。能说清这个差别，才算真正理解克隆图里那张表的作用。

递归返回值型的写法（返回克隆子树的根）比传引用型的写法更贴合树的结构，子问题的边界天然清晰，也不需要在返回前恢复现场。

顺序遍历孩子并顺序追加，孩子次序自动保持；一旦改用集合或并行处理就要显式恢复顺序。

面试视角：这题本身几行代码，考点在于面试官紧接着的追问——「如果有环怎么办」「如果节点还带一个指向任意节点的指针怎么办」，答案就是加映射表退化成克隆图或随机链表复制。准备好这条演进链，比写完 cloneTree 更重要。

易错点总结

错误写法：copy.children = root.children 直接复用原列表 → 节点虽然是新的，但两棵树共享同一个孩子容器，对新树做任何增删都会同步改动原树，深拷贝校验不通过。

错误写法：把 root 本身返回或返回 root.children 里的原节点 → 得到的是原树的别名，测试系统比对对象引用时会直接判错。

错误写法：漏掉 root == null 的出口 → 传入空树时对空引用取 val，Java 抛 NullPointerException，Go 触发空指针 panic。

错误写法：递归里不判空、改为在遍历孩子时判 child == null 跳过 → 孩子数组本身合法非空时看不出问题，但根为空的输入仍然会在函数第一行崩掉。

错误写法：新建节点后忘记初始化孩子列表，直接对 copy.children 调用 add → 若构造函数没有分配列表，字段是 null，第一次追加就抛空指针。

错误写法：用 HashSet 或其他无序容器装孩子 → 值都对但次序被打乱，[3,2,4] 可能变成 [2,3,4]，与原树不再同构。

错误写法：套用克隆图的模板，加一张 visited 映射并按值做键 → 树里出现重复值时（比如两个不同节点都是 5），第二个节点会被错误地复用为第一个的副本，结构被压扁甚至造出环。

错误写法：改写成迭代版层序克隆时，只把原节点入队而不同时把对应的新节点入队 → 出队后拿不到该往哪个新节点上挂孩子，只能再补一张映射表，反而比递归更繁琐。

错误写法：在递归中就地修改原树（例如先清空 root.children 再重建） → 破坏了输入，后续对比原树与新树的校验必然失败。

相似题目

题目	难度	考察点
133. 克隆图	中等	有环且节点可多次到达，必须靠映射表复用已建副本
138. 随机链表的复制	中等	额外的随机指针需要两趟处理，或用节点交织法省掉哈希表
100. 相同的树	简单	同构比较而非构造，两棵树同步递归并逐点比对
226. 翻转二叉树	简单	同样的后序递归骨架，但是原地改写而非新建
589. N 叉树的前序遍历	简单	只输出访问序列，适合练手写显式栈的逆序压孩子技巧
429. N 叉树的层序遍历	中等	按层分组输出，需要在队列里记录每层的边界
428. 序列化和反序列化 N 叉树	困难	孩子数不固定，序列化时必须显式编码每个节点的孩子个数