如何复制包含循环的完整非二叉树？求思路与解决方案

这个问题的核心痛点是循环引用导致的无限递归/遍历，直接用常规的树复制逻辑（边遍历边创建子节点）肯定会陷入死循环。我常用的解决思路是分两步走，靠一个「原节点-副本节点」的映射表来规避循环问题：

核心思路 #

1. 先创建所有节点副本，建立映射：不管节点间的循环关系，先遍历原树的所有节点，为每个节点创建一个副本，并把原节点和副本的对应关系存在字典里。这一步只做节点实例化，不处理子节点的关联。
2. 补全副本节点的子节点关系：再次遍历所有原节点，根据原节点的子节点列表，从映射表中取出对应的副本节点，赋值给当前副本节点的子节点列表——哪怕是循环指向的父节点/祖父节点，也能直接从映射表中找到对应的副本，不会出现找不到或重复创建的问题。

具体实现（Python示例） #

首先定义非二叉树的节点结构：

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []  # 非二叉树，子节点用列表存储

然后实现复制函数，这里用BFS遍历（也可以用DFS，逻辑一致）：

def copy_cyclic_tree(root):
    if not root:
        return None
    
    # 第一步：遍历所有节点，创建副本并建立映射
    node_map = {}
    queue = [root]
    node_map[root] = Node(root.val)
    
    while queue:
        current_original = queue.pop(0)  # BFS弹出队首节点
        for child in current_original.children:
            if child not in node_map:
                # 该节点还没创建副本，先创建并存入映射
                node_map[child] = Node(child.val)
                queue.append(child)
    
    # 第二步：为每个副本节点设置子节点（包括循环指向）
    for original_node, copy_node in node_map.items():
        for child in original_node.children:
            # 从映射表中取出子节点的副本，添加到当前副本的子列表中
            copy_node.children.append(node_map[child])
    
    return node_map[root]

验证示例 #

我们手动构造题目中描述的带循环的树，测试复制效果：

# 构造示例树：
# A的子节点是B、C
# B的子节点是G，G的子节点是B（循环）
# C的子节点是I，I的子节点是C（循环）
A = Node('A')
B = Node('B')
C = Node('C')
G = Node('G')
I = Node('I')

A.children = [B, C]
B.children = [G]
G.children = [B]
C.children = [I]
I.children = [C]

# 复制树
copied_root = copy_cyclic_tree(A)

# 验证循环结构：副本中G的子节点是副本B，B的子节点是副本G
print(copied_root.children[0].children[0].children[0].val)  # 输出: B
# 验证C的循环：副本I的子节点是副本C
print(copied_root.children[1].children[0].children[0].val)  # 输出: C

注意事项 #

• 遍历方式：BFS和DFS都可以，只要能覆盖所有节点。这里用BFS是因为逻辑直观，不容易漏节点；如果树很深，用DFS可能会栈溢出，这时候BFS更稳妥。
• 节点属性扩展：如果节点有除了val和children之外的其他属性，在创建副本时要一并复制（比如node_map[child] = Node(child.val, child.other_attr)）。
• 循环检测：映射表本身就起到了循环检测的作用——只要节点已经在映射表中，就说明已经创建过副本，不需要再处理，避免了无限遍历。

内容的提问来源于stack exchange，提问作者Veeresh Devireddy