Chương trình kiểm tra 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 (subtree) của cây thứ nhất hay không.

Ví dụ, nếu đầu vào như hình:

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

Để giải quyết, chúng ta thực hiện các bước sau:

• Định nghĩa hàm solve(). Hàm này nhận root, target
• nếu root null VÀ target null, trả về True
• nếu root null HOẶC target null, trả về False
• nếu giá trị root bằng giá trị target:
  • trả về solve(left của root, left của target) VÀ solve(right của root, right của target)
• ngược lại:
  • trả về solve(left của root, target) HOẶC solve(right của root, target)

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 is None and target is None:
            return True
        if root is None or target is 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))

Input

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)

Output

True