Chương trình kiểm tra tất cả giá trị trong cây nhị phân có giống nhau hay không trong Python

Giả sử chúng ta có một cây nhị phân, chúng ta phải kiểm tra xem tất cả các nút trong cây có cùng giá trị 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 và val
• nếu root là null, trả về True
• nếu val chưa được định nghĩa, gán val := giá trị của root
• trả về True khi giá trị của root bằng val VÀ solve(left của root, val) VÀ solve(right của root, val) đều là True

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, val=None):
        if not root:
            return True
        if val is None:
            val = root.val
        return root.val == val and self.solve(root.left, val) and self.solve(root.right, val)

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(5)
root.right = TreeNode(5)
root.left.left = TreeNode(5)
root.left.right = TreeNode(5)
print(ob.solve(root))

Input

root = TreeNode(5)
root.left = TreeNode(5)
root.right = TreeNode(5)
root.left.left = TreeNode(5)
root.left.right = TreeNode(5)

Output

True