1490.克隆N叉树

• Z时代
• 2024-01-10
• 分类：综合

1490.克隆N叉树

给定一棵 N 叉树的根节点 root ，返回该树的深拷贝（克隆）。
N 叉树的每个节点都包含一个值（ int ）和子节点的列表（ List[Node] ）。
class Node {
    public int val;
    public List<Node> children;
}
N 叉树的输入序列用层序遍历表示，每组子节点用 null 分隔（见示例）

思路

• BFS
• N叉树的遍历
• 深copy

代码

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
"""
class Solution:
    def cloneTree(self, root: "Node") -> "Node":
        if not root:
            return None
        from collections import deque
        graph = dict()
        task = deque()
        task.append(root)
        depth = 0
        tree_list = list()
        while task:
            new_task = list()
            # 遍历本层
            for node in task:
                new_node = Node(val=node.val)
                idx = graph.get(node)
                if idx:
                    parent = tree_list[idx-1]
                    parent.children.append(new_node)
                tree_list.append(new_node)
                # 遍历子节点
                for child in node.children:
                    if not child:
                        continue
                    graph[child] = len(tree_list)
                    new_task.append(child)
            task = new_task
            depth += 1
        return tree_list[0]

以上是 1490.克隆N叉树 的全部内容， 来源链接： utcz.com/z/518936.html