问题

给定一个二叉树，检查它是否是镜像对称的

例如，二叉树 [1,2,2,3,4,4,3] 是对称的
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

  1. 1<br />   / \<br />  2   2<br />   \   \<br />   3    3

进阶：
你可以运用递归和迭代两种方法解决这个问题吗？

解法一：递归

如果同时满足下面的条件，两个树互为镜像：

  • 它们的两个根结点具有相同的值

  • 每个树的右子树都与另一个树的左子树镜像对称

    class Solution {
  public boolean isSymmetric(TreeNode root) {
      if(root == null) {
          return true;
      }
      //调用递归函数，比较左节点，右节点
      return dfs(root.left,root.right);
  }

  boolean dfs(TreeNode left, TreeNode right) {
      //递归的终止条件是两个节点都为空
      //或者两个节点中有一个为空
      //或者两个节点的值不相等
      if(left == null && right == null) {
          return true;
      }
      if(left == null || right == null) {
          return false;
      }
      if(left.val != right.val) {
          return false;
      }
      //再递归的比较 左节点的左孩子 和 右节点的右孩子
      //以及比较  左节点的右孩子 和 右节点的左孩子
      return dfs(left.left,right.right) && dfs(left.right,right.left);
  }
}

  • 时间复杂度：这里遍历了这棵树，渐进时间复杂度为leetcode-101：对称二叉树 - 图1

  • 空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 leetcode-101：对称二叉树 - 图2

解法二：迭代

首先我们引入一个队列，这是把递归程序改写成迭代程序的常用方法。初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束

package leetcode_101;

import javax.swing.tree.TreeNode;
import java.util.LinkedList;

public class solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q){
        LinkedList<TreeNode> tree = new LinkedList<TreeNode>();
        tree.offer(p);
        tree.offer(q);
        while(!tree.isEmpty()){
            p = tree.poll();
            q = tree.poll();
            if(p == null && q == null) {
                continue;
            }
            if((p == null && q != null) || (p != null && q == null) || (p.val != q.val)){
                return false;
            }

            tree.offer(p.left);
            tree.offer(q.right);

            tree.offer(q.left);
            tree.offer(p.right);
        }
        return ture;
    }
}