โปรแกรมค้นหาทรีย่อยการค้นหาไบนารีที่ใหญ่ที่สุดจากทรีที่กำหนดใน Python

สมมติว่าเรามีไบนารีทรี เราต้องหาทรีย่อยที่ใหญ่ที่สุด (ด้วยจำนวนโหนดสูงสุด) เป็นทรีการค้นหาแบบไบนารี

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

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

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

• max_size :=[0]
• max_node :=[null]
• กำหนดฟังก์ชัน traverse() นี่จะใช้โหนด
• ถ้าโหนดเป็น null แล้ว
  • คืนค่า null
• left :=traverse(left of node)
• ขวา :=ข้าม (ขวาของโหนด)
• lst :=ซ้าย + [ค่าของโหนด] + ขวา
• ถ้า lst ถูกจัดเรียงแล้ว
  • ถ้า max_size[0] <ขนาดของ lst แล้ว
    • max_size[0] :=ขนาดของ lst
    • max_node[0] :=โหนด
• คืนสินค้า
• สำรวจ(ราก)
• จากวิธีหลักส่งคืน max_node[0]

ตัวอย่าง (Python)

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

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.val, end = ', ')
      print_tree(root.right)
class Solution:
   def solve(self, root):
      max_size = [0]
      max_node = [None]
      def traverse(node):
         if not node:
            return []
      left = traverse(node.left)
      right = traverse(node.right)
      lst = left + [node.val] + right
      if sorted(lst) == lst:
         if max_size[0] < len(lst):
            max_size[0] = len(lst)
            max_node[0] = node
      return lst

   traverse(root)
   return max_node[0]
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)
print_tree(ob.solve(root))

อินพุต

root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)

ผลลัพธ์

4, 5, 6,