Tổ tiên chung thấp nhất của cây tìm kiếm nhị phân trong Python

Giả sử chúng ta có một cây tìm kiếm nhị phân. chúng ta phải tìm các nút tổ tiên chung thấp nhất của hai nút đã cho. LCA của hai nút p và q thực sự là nút thấp nhất trong cây có cả p và q là số tàn. Vì vậy, nếu cây nhị phân giống như [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]. Cây sẽ như thế nào -

Ở đây LCA của 2 và 8 là 6

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

• Nếu cây trống, thì trả về null
• nếu p và q đều giống với gốc, thì trả về gốc
• left:=LCA của cây con bên trái của gốc sử dụng p và q
• right:=LCA của cây con bên phải của gốc sử dụng p và q
• nếu cả hai bên trái và bên phải đều khác 0, thì trả về gốc
• trả về trái HOẶC phải

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, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
class Solution():
   def lowestCommonAncestor(self, root, p, q):
      if not root:
         return None
      if p == root or q==root:
         return root
      left = self.lowestCommonAncestor(root.left, p, q)
      right = self.lowestCommonAncestor(root.right, p, q)
      if left and right:
         return root
      return left or right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         temp.left = TreeNode(data)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         temp.right = TreeNode(data)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
def search_node(root, element):
   if (root == None):
      return None
   if (root.data == element):
      return root
   res1 = search_node(root.left, element)
   if res1:
      return res1
   res2 = search_node(root.right, element)
   return res2

root = make_tree([6,2,8,0,4,7,9,None,None,3,5])
ob1 = Solution()
op = ob1.lowestCommonAncestor(root, search_node(root, 2), search_node(root, 8))
print(op.data)

Đầu vào

[6,2,8,0,4,7,9,null,null,3,5]
2
8

Đầu ra

6