Chương trình tìm tổ tiên chung của hai phần tử trong cây nhị phân bằng Python

Giả sử chúng ta có một cây nhị phân, và chúng ta cũng có hai số a và b, chúng ta phải tìm giá trị của nút thấp nhất có a và b là con. Chúng ta phải ghi nhớ rằng loài nút là hậu duệ của chính nó.

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

a =6, b =2, thì đầu ra sẽ là 4

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

• Xác định một phương thức giải quyết () phương thức này sẽ có gốc và a, b

• nếu root là null thì

  • trả về -1

• nếu giá trị của root là a hoặc b thì

  • giá trị trả về của root

• left:=giải quyết (bên trái của root, a, b)

• right:=giải quyết (quyền gốc, a, b)

• nếu trái hoặc phải không phải là -1, thì

  • giá trị trả về của root

• trả về trái nếu trái không giống -1 nếu ngược lại phải

• từ phương thức chính, hãy gọi giải quyết (root)

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, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

class Solution:
   def solve(self, root, a, b):
      if not root:
         return -1
      if root.val in (a, b):
         return root.val
      left = self.solve(root.left, a, b)
      right = self.solve(root.right, a, b)
      if -1 not in (left, right):
         return root.val
      return left if left != -1 else right
ob = Solution()
root = TreeNode(3)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root, 6, 2))

Đầu vào

root = TreeNode(3)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
6, 2

Đầu ra

4