数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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+ 浏览量
广告