สมมติว่าเราได้รับโหนดของต้นไม้ n-ary ในอาร์เรย์ เราต้องหาและส่งคืนโหนดรากของต้นไม้โดยการสร้างใหม่ ต้องแสดงแผนผังแบบเต็มจากโหนดที่ส่งคืนในรูปแบบการสั่งซื้อล่วงหน้า
ดังนั้นหากอินพุตเป็นแบบ
แล้วผลลัพธ์ที่ได้จะเป็น
[14, 27, 32, 42, 56, 65]
เราจะใช้รากของต้นไม้เพื่อแสดงการข้ามผ่านของต้นไม้ล่วงหน้า ดังนั้น ผลลัพธ์คือการสั่งซื้อล่วงหน้าผ่านต้นไม้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
indegree :=แผนที่ใหม่ที่มีค่าจำนวนเต็ม
-
สำหรับแต่ละโหนดในทรี ให้ทำ
-
สำหรับเด็กแต่ละคนในลูกชี้ของโหนด ทำ
-
indegree[value of child] :=indegree[value of child] + 1
-
-
-
สำหรับแต่ละโหนดในทรี ให้ทำ
-
ถ้า indegree[value of node] เท่ากับ 0 แล้ว
-
โหนดกลับ
-
-
-
คืนค่า null
ตัวอย่าง (Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
import collections
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(tree):
indegree = collections.defaultdict(int)
for node in tree:
for child in node.children:
indegree[child.val] += 1
for node in tree:
if indegree[node.val] == 0:
return node
return None
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])
tree = [node2, node1, node5, node3, node6, node4]
root = solve(tree)
print(treeprint(root, None)) อินพุต
node6 = Node(65) node5 = Node(56) node4 = Node(42, [node5, node6]) node3 = Node(32) node2 = Node(27) node1 = Node(14, [node2, node3, node4]) tree = [node2, node1, node5, node3, node6, node4]
ผลลัพธ์
[14, 27, 32, 42, 56, 65]
