Chương trình kiểm tra mỗi nút (trừ lá) có giá trị bằng tổng hai nút con 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 với mọi nút trong cây trừ các lá, giá trị của nó có bằng tổng giá trị nút con trái và nút con phải 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 dfs(). Hàm này nhận root
• nếu root là null, trả về True
• nếu left của root null VÀ right của root null, trả về True (là lá)
• left := 0
• nếu left của root không null, left := giá trị left của root
• right := 0
• nếu right của root không null, right := giá trị right của root
• trả về True khi (left + right bằng giá trị root) VÀ dfs(left của root) VÀ dfs(right của root)
• Từ phương thức chính: trả về dfs(root)

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):
        def dfs(root):
            if root is None:
                return True
            if root.left is None and root.right is None:
                return True
            left = 0
            if root.left:
                left = root.left.val
            right = 0
            if root.right:
                right = root.right.val
            return (left + right == root.val) and dfs(root.left) and dfs(root.right)
        return dfs(root)

ob = Solution()
root = TreeNode(18)
root.left = TreeNode(8)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)
print(ob.solve(root))

Input

root = TreeNode(18)
root.left = TreeNode(8)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)

Output

True