leetcode | 101.对称二叉树

101.对称二叉树

题目描述

给你一个二叉树的根节点 root ， 检查它是否轴对称。

题目链接

代码

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def isSymmetric(self, root):
        """
        递归法
        
        两个树互为镜像：
            它们的两个根结点具有相同的值
            每个树的右子树都与另一个树的左子树镜像对称
        :type root: TreeNode
        :rtype: bool
        """
        return self.check(root, root)
    
    def check(self, p, q):
        if not p and not q:
            return True
        if not p or not q:
            return False
        return p.val == q.val and self.check(p.left, q.right) and self.check(p.right, q.left)
    
    def isSymmetric1(self, root):
        """迭代法"""
        queue = list()
        queue.append(root)
        queue.append(root)
        while len(queue) != 0:
            t1 = queue.pop(0)
            t2 = queue.pop(0)
            if not t1 and not t2:
                continue
            if not t1 or not t2:
                return False
            if t1.val != t2.val:
                return False
            queue.append(t1.left)
            queue.append(t2.right)
            queue.append(t1.right)
            queue.append(t2.left)
        return True


if __name__ == "__main__":
    root = TreeNode(1)
    node2 = TreeNode(2)
    node3 = TreeNode(2)
    node4 = TreeNode(3)
    node5 = TreeNode(4)
    node6 = TreeNode(4)
    node7 = TreeNode(3)
    
    slt = Solution()
    # result = slt.isSymmetric(root)
    result = slt.isSymmetric(root)
    print(result)