โจทย์
ได้รับ Root ของ N-ary Tree ต้องสร้าง Copy ของ Tree ทั้งหมด (Deep Copy) แล้วแสดง Preorder ของทั้งต้นฉบับและ Copy (จะเหมือนกันทุกอย่าง)
อัลกอริธึม (BFS กับ Queue)
- สร้าง Node ใหม่สำหรับ Root
- ใช้ Deque เก็บคู่ (Original Node, Cloned Node)
- วนลูป Dequeue แล้ว Clone ลูกทุกตัว นำเข้าคิวต่อ
โค้ด Python
from collections import deque
class Node:
def __init__(self, value, child=None) -> None:
self.val = value
self.children = []
if child:
for v in child:
self.children.append(v)
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 is None:
tree.append("None")
return tree
if tree is None:
tree = []
tree.append(node.val)
for child in node.children:
treeprint(child, tree)
return tree
# สร้าง 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)) # Output: [14, 27, 32, 42, 56, 65]
Input / Output
Input: Root of original tree
Output: [14, 27, 32, 42, 56, 65] (Preorder of cloned tree)
