LeetCode 101. 对称二叉树

101. 对称二叉树

题目

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

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

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

进阶：

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

解题思路

如何去判断二叉树是镜像对称？如下：

根节点为 null，直接返回 True；
当根节点不为 null 时，判断左右子树是否对称：
- 判断 root.left 跟 root.right 节点值是否相同
- 判断 root.left 的左子树是否与 root.right 的右子树对称
- 判断 root.left 的右子树是否与 root.right 的左子树对称

按照题目中【进阶】部分所述，本篇幅就从递归和迭代两种思路来解决该问题。

思路：递归

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

如果都为空指针的情况下，返回 True
其中一个不为空的情况下，返回 False

递归具体的过程：

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

具体代码实现见【代码实现：递归】。

思路：迭代

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

具体的做法：

初始化的时候，将根节点入队两次。
循环的时候，每次出队两次提取两个节点，比较它们的值（因为子树互为镜像，它们的值应该是相等的）
再次入队时，将两个节点的左右子节点按照相反的顺序进行入队。（例如： 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:      
        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)

代码实现：迭代

# 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

实现结果

实现结果：递归

实现结果：迭代

总结

根据题意，按照递归和迭代的思路解决该问题
具体的判断是否为镜像对称的思路：
- 这里判断 root 不为空的情况（根节点为空，直接返回 True）；
- 判断 root.left 和 root.right 节点值是否相同；
- 判断 root.left 的左子树和 root.right 的右子树是否对称；
- 判断 root.left 的右子树和 root.right 的左子树是否对称。
递归实现具体的过程：
- 终止条件：指针都会空时，返回 True；其中一个指针为空时，返回 False；
- 判断两个指针的节点值是否相同；
- 判断 t1 的左子树是否与 t2 的右子树对称
- 判断 t1 的右子树是否与 t2 的左子树对称
迭代实现的具体过程：
- 这里需要引入一个队列，首先初始化队列，先将 root 入队两次；
- 循环开始，先连续出队两次，提取两个节点，比较它们的值（两个相邻的值应该是相等的，因为左右子树互为镜像）
- 将两个节点的左右子节点按照相反的顺序进行入队（例如 t1 的左节点与 t2 的右节点连续入队）
- 循环结束的条件，当队列为空的时候，或者出队的两个节点不相等（也就是不对称）。

欢迎关注微信公众号《书所集录》

LeetCode 101. 对称二叉树 | Python