101. 对称二叉树
题目
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
解题思路
如何去判断二叉树是镜像对称？如下：
- 根节点为 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 的右节点连续入队）
- 循环结束的条件，当队列为空的时候，或者出队的两个节点不相等（也就是不对称）。
欢迎关注微信公众号《书所集录》
网友评论