Tìm cây con lớn nhất có cây con trái và phải giống hệt nhau trong 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 có cây con bên trái và bên phải giống hệt nhau. Độ phức tạp thời gian ưu tiên là O (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 -

• Định nghĩa một hàm giải quyết (). Điều này sẽ root, mã hóa, maxSize, maxNode

• nếu gốc là Không thì

  • trả về 0

• left_list:=danh sách với một chuỗi trống

• right_list:=danh sách với một chuỗi trống

• ls:=giải quyết (root.left, left_list, maxSize, maxNode)

• rs:=giải quyết (root.right, right_list, maxSize, maxNode)

• kích thước:=ls + rs + 1

• nếu left_list [0] giống right_list [0] thì

  • nếu kích thước> maxSize [0], thì

    • maxSize [0]:=size

    • maxNode [0]:=root

• encode [0]:=encode [0] nối "|" nối left_list [0] nối "|"

• encode [0]:=encode [0] nối "|" nối str (root.data) nối "|"

• encode [0]:=encode [0] nối "|" nối ngay danh sách [0] nối "|"

• kích thước trả lại

• Từ phương thức chính, thực hiện như sau -

• tối đa:=[0]

• encode:=list với một chuỗi trống

• giải quyết (nút, mã hóa, tối đa, maxNode)

• trả lại tối đa

Ví dụ

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

Đầu vào

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)

Đầu ra

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