Python实现N叉树复制程序

假设，我们得到了一棵N叉树，其根节点为'root'。我们需要复制整个N叉树并对两棵树进行前序遍历。复制后的树需要使用另一个根节点存储。树的节点结构如下所示：

Node:
   value : <integer>
   children : <array>

所以，如果输入类似于

，那么输出将是

[14, 27, 32, 42, 56, 65]

输入树和输出树的前序表示将相同，因为已创建了树的精确副本。

为了解决这个问题，我们将遵循以下步骤：

  • 如果root不为空，则

    • 返回root

  • head := 一个具有root值的新节点

  • q := 一个包含元素root和head的新双端队列

  • 当q不为空时，执行以下操作

    • node := 从q中弹出第一个元素

    • cloned := 从q中弹出第一个元素

    • 对于node.children中的每个chld，执行以下操作

      • new_n := 一个包含chld值的新节点

      • 将new_n添加到cloned的子节点中

      • 将chld和new_n插入到q的末尾

  • 返回head

示例（Python）

让我们看看以下实现，以更好地理解：

 在线演示

from queue import deque
class Node:
   def __init__(self, value, child = None) -> None:
      self.val = value
      self.children = []
      if child != None:
         for value in child:
            self.children.append(value)

def solve(root):
   if not root:
      return root
   head = Node(root.val)
   q = deque([(root, head)])
   while q:
      node, cloned = q.popleft()
      for chld in node.children:
         new_n = Node(chld.val)
         cloned.children.append(new_n)
         q.append((chld,new_n))
   return head

def treeprint(node, tree):
   if node == None:
      tree.append("None")
      return tree
   if tree == None:
      tree = []
   tree.append(node.val)
   for child in node.children:
      treeprint(child, tree)
   return tree

node6 = Node(65)
node5 = Node(56)
node4 = Node(42, [node5, node6])
node3 = Node(32)
node2 = Node(27)
node1 = Node(14, [node2, node3, node4])
root = node1

copynode = solve(root)
print(treeprint(copynode, None))

输入

node6 = Node(65)
node5 = Node(56)
node4 = Node(42, [node5, node6])
node3 = Node(32)
node2 = Node(27)
node1 = Node(14, [node2, node3, node4])
root = node1

输出

[14, 27, 32, 42, 56, 65]

更新于: 2021年5月18日

1K+ 浏览量

开启你的职业生涯

通过完成课程获得认证

开始学习
广告