LeetCode刷题 NO.101 对称二叉树 (简单)

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

解析

1）树结构最直观的解法，就是递归；

2）判断对称，有点像照镜子，即左边的左子树等于右边的右子树，左边的右子树等于右边的左子树。

代码示例

1、递归解法

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

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        # 将根节点作为左右初始节点
        return self.recursion(root, root)

    def recursion(self, left, right):
        if left == None and right == None:
            return True
        if (left == None and right) or (left and right == None):
            return False
        if left.val != right.val:
            return False
        return self.recursion(left.left, right.right) and \
            self.recursion(left.right, right.left)

2、队列解法

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root == None or (not root.left and not root.right):
            return True
        queue = [root.left, root.right]
        while queue:
            # 从队列中一次取出两个节点，再比较这两个节点
            v1 = queue.pop(0)
            v2 = queue.pop(0)
            if (v1 == None and v2) or (v1 and v2 == None):
                return False
            # 都为空则跳过
            if not v1 and not v2:
                continue
            if v1.val != v2.val:
                return False
            # 将左节点的左孩子， 右节点的右孩子放入队列
            queue.append(v1.left)
            queue.append(v2.right)
            # 将左节点的右孩子， 右节点的左孩子放入队列
            queue.append(v1.right)
            queue.append(v2.left)
        return True

执行用时：32 ms, 在所有 Python3 提交中击败了 95.53% 的用户.