给定二叉树的根节点 root，判断它是否 轴对称（镜像对称）
题目：给你一个二叉树的根节点 root ， 检查它是否轴对称。这个题的思路是，把「轴对称」转化为「两棵子树互为镜像」的问题：
[*]递归比较：左子树的左孩子 vs 右子树的右孩子，左子树的右孩子 vs 右子树的左孩子。
[*]迭代法：可用队列/栈每次成对弹出节点比较。
复杂度：
时间复杂度：O(n)，每个节点访问一次
空间复杂度：
[*]递归：O(h)（栈深度）
[*]迭代：O(n)（队列最大宽度）
1、递归比较
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
if(root.left==null && root.right==null){
return true;
}
if(root.left==null || root.right==null){
return false;
}
// 判断左右子树是否镜像对称
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode t1, TreeNode t2){
if(t1==null && t2==null){
return true;
}
if(t1==null || t2==null){
return false;
}
// 递归比较：
// 1.左子树 vs 右子树
// 2.左子树的左孩子 vs 右子树的右孩子
// 3.左子树的右孩子 vs 右子树的左孩子
if(t1.val == t2.val && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left)){
return true;
}else{
return false;
}
}
}2、迭代法（队列双指针）
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root.left);
q.offer(root.right);
while (!q.isEmpty()) {
TreeNode t1 = q.poll();
TreeNode t2 = q.poll();
if (t1 == null && t2 == null) continue;
if (t1 == null || t2 == null || t1.val != t2.val) return false;
q.offer(t1.left);q.offer(t2.right);
q.offer(t1.right); q.offer(t2.left);
}
return true;
}
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]