LeetCode 1490. 克隆 N 叉树

Categories:

题目描述
思路分析
1. 解法一：递归克隆（推荐）
相似题目

题目描述

✅ 1490. 克隆 N 叉树

思路分析

解法一：递归克隆（推荐）

核心思路：

N 叉树无环，可直接递归复制节点。

新节点的子节点列表由递归结果组成。

空节点直接返回空。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(h)，递归栈深度与树高相关。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public Node cloneTree(Node root) {
        if (root == null) {
            return null;
        }

        Node node = new Node(root.val);
        node.children = new ArrayList<>();
        for (Node child : root.children) {
            node.children.add(cloneTree(child));
        }

        return node;
    }
}

func cloneTree(root *Node) *Node {
	if root == nil {
		return nil
	}

	node := &Node{Val: root.Val}
	if len(root.Children) == 0 {
		return node
	}

	node.Children = make([]*Node, 0, len(root.Children))
	for _, child := range root.Children {
		node.Children = append(node.Children, cloneTree(child))
	}

	return node
}

相似题目

题目	难度	考察点
133. 克隆图	中等	DFS/BFS
589. N 叉树的前序遍历	简单	递归
590. N 叉树的后序遍历	简单	递归
429. N 叉树的层序遍历	中等	BFS
559. N 叉树的最大深度	简单	递归

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/28585165