给定二叉树的根节点 root，判断它是否 轴对称（镜像对称）

题目：给你一个二叉树的根节点 root ， 检查它是否轴对称。

这个题的思路是，把「轴对称」转化为「两棵子树互为镜像」的问题：

• 递归比较：左子树的左孩子 vs 右子树的右孩子，左子树的右孩子 vs 右子树的左孩子。
  
• 迭代法：可用队列/栈每次成对弹出节点比较。
  

复杂度：
时间复杂度：O(n)，每个节点访问一次
空间复杂度：

• 递归：O(h)（栈深度）
  
• 迭代：O(n)（队列最大宽度）
  

1、递归比较

1. class Solution {
2.     public boolean isSymmetric(TreeNode root) {
3.         if(root==null){
4.             return true;
5.         }
6.         if(root.left==null && root.right==null){
7.             return true;
8.         }
10.         if(root.left==null || root.right==null){
11.             return false;
12.         }
13.    
14.         // 判断左右子树是否镜像对称
15.         return isMirror(root.left, root.right);
16.         
17.     }
19.     private boolean isMirror(TreeNode t1, TreeNode t2){
20.         if(t1==null && t2==null){
21.             return true;
22.         }
24.         if(t1==null || t2==null){
25.             return false;
26.         }
27.         // 递归比较：
28.         // 1.左子树 vs 右子树
29.         // 2.左子树的左孩子 vs 右子树的右孩子
30.         // 3.左子树的右孩子 vs 右子树的左孩子
31.         if(t1.val == t2.val && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left)){
32.             return true;
33.         }else{
34.             return false;
35.         }
36.     }
37. }

复制代码

2、迭代法（队列双指针）

1. class Solution {
2.     public boolean isSymmetric(TreeNode root) {
3.         if (root == null) return true;
4.         Queue<TreeNode> q = new LinkedList<>();
5.         q.offer(root.left);
6.         q.offer(root.right);
8.         while (!q.isEmpty()) {
9.             TreeNode t1 = q.poll();
10.             TreeNode t2 = q.poll();
11.             if (t1 == null && t2 == null) continue;
12.             if (t1 == null || t2 == null || t1.val != t2.val) return false;
13.             q.offer(t1.left);  q.offer(t2.right);
14.             q.offer(t1.right); q.offer(t2.left);
15.         }
16.         return true;
17.     }
18. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！