Cây đối xứng trong Python

Kiểm tra cây nhị phân có đối xứng không (giống hình ảnh gương).

Giải pháp

Đệ quy so sánh hai cây con:

• Hàm solve(node1, node2).
• Nếu cả hai rỗng → True.
• Nếu một rỗng → False.
• Trả về node1.val == node2.val AND solve(node1.left, node2.right) AND solve(node1.right, node2.left).

Ví dụ

Triển khai Python:

class TreeNode: 
    def __init__(self, data, left = None, right = None): 
        self.data = data 
        self.left = left 
        self.right = right 
# ... (hàm hỗ trợ tạo cây) 
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) 
tree1 = make_tree([1,2,2,3,4,4,3]) 
tree2 = make_tree([1,2,2,3,4,None,3]) 
ob1 = Solution() 
print(ob1.isSymmetric(tree1)) 
print(ob1.isSymmetric(tree2))

Đầu vào

tree1 = make_tree([1,2,2,3,4,4,3]) tree2 = make_tree([1,2,2,3,4,None,3])

Đầu ra

True False