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

Giả sử chúng ta có một cây 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ư [3,5,1,6,2,0,8, null, null, 7,4]. Cây sẽ như thế nào -

Ở đây LCA của 5 và 1 là 3

Để 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
• quay lại trái HOẶC phải

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

Ví dụ

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
         if (not temp.right):
            if data is not None:
               temp.right = TreeNode(data)
            else:
               temp.right = TreeNode(0)
            break
         else:
            que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution(object):
   def lowestCommonAncestor(self, root, p, q):
      if not root:
         return None
      if root.data == p or root.data ==q:
         return root
      left = self.lowestCommonAncestor(root.left, p, q)
      right = self.lowestCommonAncestor(root.right, p, q)
      if right and left:
         return root
      return right or left
ob1 = Solution()
tree = make_tree([3,5,1,6,2,0,8,None,None,7,4])
print(ob1.lowestCommonAncestor(tree, 5, 1).data)

Đầu vào

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

Đầu ra

3