一、题目
1、算法题目
“给定二叉树的根节点，检查它是否轴对称。”
题目链接：
来源：力扣（LeetCode）
链接：101. 对称二叉树 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个二叉树的根节点 root ， 检查它是否轴对称。
网络异常，图片无法展示
|
示例 1： 输入： root = [1,2,2,3,4,4,3] 输出： true 复制代码
示例 2： 输入： root = [1,2,2,null,3,null,3] 输出： false 复制代码
二、解题
1、思路分析
这道题是检查二叉树是否轴对称，如果这个树的左右子树镜像对称，那么这个树是对称的。
因此，可以将问题转化为，两个树在什么条件下互为镜像：
- 两个跟节点具有相同的值。
- 每个树的右子树都与另一个树的左子树镜像对称。
那么就可以编写一个递归函数，通过两个指针来遍历这棵树，指针开始都指向树的根，随后p指针向右，q指针向左；q指针向右，p指针向左。
每次先检查节点的值是否相同，再判断左右子树是否对称。
2、代码实现
代码参考：
class Solution { public boolean isSymmetric(TreeNode root) { return check(root, root); } public boolean check(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p == null || q == null) { return false; } return p.val == q.val && check(p.left, q.right) && check(p.right, q.left); } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n)
遍历了这棵树，时间复杂度为O(n)。
空间复杂度： O(n)
递归层数不超过n，空间复杂度为O(n)。
三、总结
我们使用递归的方法实现了对对称性的判断。
首先，判断根节点的值，然后判断左右子树的值是否相等，然后判断结构是否相同。
