在Python中创建n叉树的复制程序
假设我们已经提供了一棵n叉树,其根节点是’root’。我们必须创建一份完整的n叉二叉树的副本,并对两棵树都执行先序遍历。副本树必须使用另一个根节点存储。树的节点结构如下-。
Node:
value : <integer>
children : <array>
因此,如果输入是这样的
,则输出将是
[14,27,32,42,56,65]
输入树和输出树的先序表示将相同,因为已经创建了树的精确副本。
为解决这个问题,我们将按照以下步骤操作-
- 如果root不为空,则
- 返回root
- 让head是一个带有root值的新节点
- q是一个包含元素root和head的新deque
- 当q不为空时,执行以下操作
- 从q中弹出第一个元素作为node
- 从q中弹出第一个元素,将其称为cloned
- 对于每个chld在node.children中,执行以下操作
- new_n是一个包含chld值的新节点
- 将new_n添加到克隆的子节点中
- 将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]