สมมติว่าเราได้รับต้นไม้ n-ary และบอกว่าให้กำหนดเส้นผ่านศูนย์กลางของต้นไม้ เส้นผ่านศูนย์กลางของต้นไม้เป็นเส้นทางที่ยาวที่สุดซึ่งอยู่ระหว่างโหนดสองใบของต้นไม้ เราต้องหาและคืนค่าจำนวนเต็มที่แทนเส้นผ่านศูนย์กลางของต้นไม้
ดังนั้นหากอินพุตเป็นแบบ
แล้วผลลัพธ์จะเป็น 3
เส้นผ่านศูนย์กลางของต้นไม้ n-ary นี้ประกอบด้วยขอบ 27->14, 14->42 และ 42->56 หรือ 42->65 (ทำเครื่องหมายในแผนภาพด้วยเส้นสีแดง) ความยาวของเส้นทางคือ 3
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ตอบ :=1
-
กำหนดฟังก์ชั่นความลึก() สิ่งนี้จะหยั่งราก
-
ถ้ารูทไม่ว่าง
-
คืนค่า 0
-
-
ลูก :=รายการใหม่ที่มีค่า 0, 0
-
temp_children :=รายการใหม่
-
สำหรับเด็กแต่ละคนในลูกของรูตทำ
-
แทรกความลึก (ลูก) ที่ส่วนท้ายของ temp_children
-
-
ถ้าขนาดของ (temp_children)> 0 แล้ว
-
ลูก :=temp_children
-
-
ans :=สูงสุดของ ans, sum(เรียงลำดับรายการลูก [จากความยาวดัชนีของ (ลูก)- 2 ถึงปลาย]) + 1
-
ส่งคืนเด็กสูงสุด + 1
-
-
ความลึก(ราก)
-
กลับมา (ans -1)
ตัวอย่าง (Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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) ans = 1 def solve(root): def depth(root): global ans if not root: return 0 children = [0, 0] temp_children = [depth(child) for child in root.children] if len(temp_children) > 0: children = temp_children ans = max(ans, sum(sorted(children)[-2:]) + 1) return max(children) + 1 depth(root) return ans -1 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 print(solve(root))
อินพุต
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
ผลลัพธ์
3
