資料結構
網路
關係型資料庫管理系統
作業系統
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+ 瀏覽量
廣告