每日一道leetcode101. 对称二叉树

2021.07.22

给定一个二叉树，检查它是否是镜像对称的。

 

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
 

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3
 

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：递归
根据上面判断二叉树是否对称的思路，先设定递归终止的条件：

如果都为空指针的情况下，返回 True
其中一个不为空的情况下，返回 False
递归具体的过程：

先判断当前两个指针节点值是否相等
判断 t1 的左子树与 t2 的右子树是否对称
判断 t1 的右子树与 t1 的左子树是否对称

# 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: TreeNode) -> bool:
        return self.check(root, root)
    def check(self, t1, t2):
        if t1 == None and t2 == None:
            return True
        if t1 == None or t2 == None:
            return False
        return t1.val == t2.val and self.check(t1.left,t2.right) and self.check(t1.right,t2.left)

思路：迭代
还是按照开篇的思路判断二叉树的对称，这次使用迭代的方法实现。这里需要引入一个队列。

具体的做法：

初始化的时候，将根节点入队两次。
循环的时候，每次出队两次提取两个节点，比较它们的值（因为子树互为镜像，它们的值应该是相等的）
再次入队时，将两个节点的左右子节点按照相反的顺序进行入队。（例如： t1 节点的左子节点跟 t2 节点的右子节点连续入队）
循环结束的条件，当队列为空的时候，或者连续出队的两个节点不相等时。

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

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # 构建，初始化队列
        # 将根节点入队两次
        queue = []
        queue.append(root)
        queue.append(root)

        # 循环开始
        while len(queue) != 0:
            # 先连续出队，提取两个节点进行比较
            t1 = queue.pop()
            t2 = queue.pop()

            if t1 == None and t2 == None:
                continue
            # 当两个节点不相等，直接返回 False
            if t1 == None or t2 == None or t1.val != t2.val:
                return False

            # 重新入队，将两个节点的左右子节点按照相反的顺序入队
            queue.append(t1.left)
            queue.append(t2.right)

            queue.append(t1.right)
            queue.append(t2.left)
        
        return True