/题目描述

image.png

解决思路

递归

image.png

  1.      public boolean isSymmetric(TreeNode root) {
  2.         return isMirror(root,root);
  3.     }
  5.     //判断镜像t1和镜像t2
  6.     public boolean isMirror(TreeNode t1,TreeNode t2){
  7.         if(t1==null&&t2==null)
  8.             return true;
  9.         if(t1==null||t2==null)
  10.             return false;
  11.         return (t1.val==t2.val)&&isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);
  12.     }

复杂度分析

时间复杂度：O(n)，因为我们遍历整个输入树一次，所以总的运行时间为 O(n)，其中 nn 是树中结点的总数。

空间复杂度：递归调用的次数受树的高度限制。在最糟糕情况下，树是线性的，其高度为 O(n)。因此，在最糟糕的情况下，由栈上的递归调用造成的空间复杂度为 O(n)。

迭代

除了递归的方法外，我们也可以利用队列进行迭代。队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像。最初，队列中包含的是 root 以及 root。该算法的工作原理类似于 BFS，但存在一些关键差异。每次提取两个结点并比较它们的值。然后，将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。

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

复杂度分析

时间复杂度：O(n)，因为我们遍历整个输入树一次，所以总的运行时间为 O(n)，其中 nn 是树中结点的总数。
空间复杂度：搜索队列需要额外的空间。在最糟糕情况下，我们不得不向队列中插入 O(n)个结点。因此，空间复杂度为 O(n)。