Chương trình kiểm tra xem một cây có phải là cây con của cây khác hay không trong Python

Giả sử chúng ta có hai cây nhị phân. Chúng ta phải kiểm tra xem cây thứ hai có phải là cây con của cây đầu tiên hay không.

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

thì đầu ra sẽ là True.

Để 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ẽ bắt rễ, nhắm mục tiêu

• nếu root là null và target cũng là null thì

  • trả về True

• nếu root là null hoặc target là null thì

  • trả về Sai

• nếu giá trị của gốc giống với giá trị của đích thì

  • trả về giải quyết (bên trái của thư mục gốc, bên trái của mục tiêu) và giải quyết (bên phải của thư mục gốc, bên phải của mục tiêu)

• nếu không,

  • trả về giải quyết (bên trái của thư mục gốc, đích) hoặc giải quyết (bên phải của thư mục gốc, mục tiêu)

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.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root, target):
      if root == None and target == None:
         return True
      if root == None or target == None:
         return False
      if root.val == target.val:
         return self.solve(root.left, target.left) and
self.solve(root.right, target.right)
      else:
         return self.solve(root.left, target) or
self.solve(root.right, target)
ob = Solution()
root1 = TreeNode(6)
root1.left = TreeNode(4)
root1.right = TreeNode(10)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)
root2 = TreeNode(4)
root2.left = TreeNode(3)
root2.right = TreeNode(5)
print(ob.solve(root1, root2))

Đầu vào

root1 = TreeNode(6)
root1.left = TreeNode(4)
root1.right = TreeNode(10)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)
root2 = TreeNode(4)
root2.left = TreeNode(3)
root2.right = TreeNode(5)

Đầu ra

True