Chương trình tìm cây con tìm kiếm nhị phân lớn nhất từ ​​một cây nhất định bằng Python

Giả sử chúng ta có một cây nhị phân, chúng ta phải tìm cây con lớn nhất (với số nút tối đa) là cây tìm kiếm nhị phân.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• max_size:=[0]
• max_node:=[null]
• Định nghĩa một hàm traverse (). Điều này sẽ lấy nút
• nếu nút là null, thì
  • trả về null
• left:=traverse (bên trái của nút)
• right:=traverse (bên phải của nút)
• lst:=left + [giá trị của nút] + right
• nếu lst được sắp xếp, thì
  • nếu max_size [0]
  • max_size [0]:=kích thước của lst
  • max_node [0]:=nút

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

4, 5, 6,