Chương trình kiểm tra cây nhị phân có đối xứng (symmetric) 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 cây đó có phải là cây đối xứng (symmetric tree) hay không. Một cây được gọi là đối xứng nếu nó giống hệt khi lấy ảnh gương của nó. Từ hai cây này, cái đầu tiên là đối xứng, nhưng cái thứ hai không.

Để giải quyết, chúng ta sẽ thực hiện các bước sau theo đệ quy. Hàm sẽ là solve(root, root):

• nếu node1 và node2 đều rỗng, trả về True
• nếu node1 hoặc node2 rỗng, trả về False
• trả về True khi node1.val = node2.val VÀ solve(node1.left, node2.right) VÀ solve(node1.right, node2.left)

Ví dụ

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class Solution(object):
    def isSymmetric(self, root):
        return self.solve(root, root)

    def solve(self, node1, node2):
        if not node1 and not node2:
            return True
        if not node1 or not node2:
            return False
        return node1.data == node2.data and self.solve(node1.left, node2.right) and self.solve(node1.right, node2.left)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)
ob1 = Solution()
print(ob1.isSymmetric(root))

Input

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)

Output

True