home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

ค้นหาแผนผังย่อยที่ใหญ่ที่สุดที่มีแผนผังย่อยด้านซ้ายและขวาเหมือนกันใน Python

สมมุติว่าเรามีไบนารีทรี เราต้องหา subtree ที่ใหญ่ที่สุดที่มี subtree ด้านซ้ายและขวาเหมือนกัน ความซับซ้อนของเวลาที่ต้องการคือ O(n)

ดังนั้นหากอินพุตเป็นแบบ

ค้นหาแผนผังย่อยที่ใหญ่ที่สุดที่มีแผนผังย่อยด้านซ้ายและขวาเหมือนกันใน Python

แล้วผลลัพธ์ที่ได้จะเป็น

ค้นหาแผนผังย่อยที่ใหญ่ที่สุดที่มีแผนผังย่อยด้านซ้ายและขวาเหมือนกันใน Python

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • กำหนดฟังก์ชัน Solve() การดำเนินการนี้จะทำการรูท, เข้ารหัส, maxSize, maxNode

  • ถ้า root เป็น None แล้ว

    • คืนค่า 0

  • left_list :=รายการที่มีสตริงว่าง

  • right_list :=รายการที่มีสตริงว่าง

  • ls :=แก้ (root.left, left_list, maxSize, maxNode)

  • rs :=แก้ (root.right, right_list, maxSize, maxNode)

  • ขนาด :=ls + rs + 1

  • ถ้า left_list[0] เหมือนกับ right_list[0] แล้ว

    • ถ้า size> maxSize[0] แล้ว

      • maxSize[0] :=ขนาด

      • maxNode[0] :=รูท

  • encode[0] :=encode[0] ต่อกัน "|" concatenate left_list[0] ต่อ "|"

  • encode[0] :=encode[0] ต่อกัน "|" เชื่อม str(root.data) ต่อกัน "|"

  • encode[0] :=encode[0] ต่อกัน "|" concatenate right_list[0] ต่อ "|"

  • ขนาดคืน

  • จากวิธีหลัก ให้ทำดังนี้ −

  • สูงสุด :=[0]

  • เข้ารหัส :=รายการที่มีสตริงว่าง

  • แก้ (โหนด, เข้ารหัส, สูงสุด, maxNode)

  • ผลตอบแทนสูงสุด

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

class TreeNode:
   def __init__(self, data):
      self.data = data
      self.left = self.right = None
def solve(root, encode, maxSize, maxNode):
   if (root == None):
      return 0
   left_list = [""]
   right_list = [""]
   ls = solve(root.left, left_list, maxSize, maxNode)
   rs = solve(root.right, right_list, maxSize, maxNode)
   size = ls + rs + 1
   if (left_list[0] == right_list[0]):
      if (size > maxSize[0]):
         maxSize[0] = size
         maxNode[0] = root
   encode[0] = encode[0] + "|" + left_list[0] + "|"
   encode[0] = encode[0] + "|" + str(root.data) + "|"
   encode[0] = encode[0] + "|" + right_list[0] + "|"

   return size

def largestSubtree(node, maxNode):
   maximum = [0]
   encode = [""]
   solve(node, encode, maximum,maxNode)
   return maximum
root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)
maxNode = [None]
maximum = largestSubtree(root, maxNode)
print("Root of largest sub-tree",maxNode[0].data)
print("and its size is ", maximum)

อินพุต

root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)

ผลลัพธ์

Root of largest sub-tree 70
and its size is [7]