ต้นไม้สมมาตรใน Python

สมมติว่าเรามีต้นไม้แบบทวิภาคหนึ่งต้น เราต้องตรวจสอบว่าต้นไม้นั้นเป็นต้นไม้สมมาตรหรือไม่ ต้นไม้จะถูกว่าสมมาตรถ้ามันเหมือนเดิมเมื่อเราหาภาพกระจกของมัน จากต้นไม้สองต้น ต้นแรกเป็นสมมาตร แต่ต้นที่สองไม่ใช่

วิธีการแก้ปัญหา

• เราจะเรียกขั้นตอนต่อไปนี้แบบเรียกซ้ำ ฟังก์ชันจะเป็น solve(root, root)
• ถ้า node1 และ node2 ว่าง ให้คืนค่า true
• ถ้า node1 หรือ node2 ว่าง ให้คืนค่า false
• คืนค่า true เมื่อ node1.val = node2.val และ solve(node1.left, node2.right) และ solve(node1.right, node2.left)

ตัวอย่าง

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

def insert(temp, data):
    que = []
    que.append(temp)
    while len(que):
        temp = que[0]
        que.pop(0)
        if not temp.left:
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        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))

อินพุต

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

เอาต์พุต

True False