方法一：二叉树递归（递归过程符合思考逻辑）

注意最后一句，每棵子树都要对称

1. 终止条件：子问题结点是否对称 2. 返回值： 每一级将子问题是否匹配的结果往上传递。

最坏情况下，时间复杂度为O(n),二叉树递归和计算中的复杂递归不同，这里的递归就是遍历！

• step 1：两种方向的前序遍历，同步过程中的当前两个节点，同为空，属于对称的范畴。
• step 2：当前两个节点只有一个为空或者节点值不相等，已经不是对称的二叉树了。
• step 3：第一个节点的左子树与第二个节点的右子树同步递归对比，第一个节点的右子树与第二个节点的左子树同步递归比较。

  public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot==null)return true;
        return compareNode(pRoot.left,pRoot.right);
    }
    boolean compareNode(TreeNode left,TreeNode right){
        if(left==null) return right==null;
        if(right==null) return left==null;
        if(left.val!=right.val)return false;
        return compareNode(left.right,right.left)&&compareNode(left.left,right.right);
    }
  }

  方法二：两个队列分别从两边层序遍历

  boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot==null)return true;
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        q1.offer(pRoot.left);
        q2.offer(pRoot.right);//先比较第二层两个子结点
        while(q1.size()!=0||q2.size()!=0){
            TreeNode lNode = q1.poll();
            TreeNode rNode = q2.poll();
            if(lNode==null&&rNode==null)continue;
            //结点数值不同或存在一个为null，则不对称
            if(lNode==null||rNode==null||lNode.val!=rNode.val)return false;
            //q1从左至右层次遍历
            q1.offer(lNode.left);
            q1.offer(lNode.right);
            //q2从右至左层次遍历
            q2.offer(rNode.right);
            q2.offer(rNode.left);
        }
        return true;//遍历过后没出现不对称的情况就返回true
    }

  两种方法时间复杂度空间复杂度一致，时间上都是一次完整遍历，空间上一个是开辟递归栈空间，一个是队列存储空间，这两个空间都与结点数量n相关。