题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路：
当根为空，是对称的，不为空就开始比较。比较左子树A和右子树B。
然后比较的是左子树的左节点和右子树的右节点。左子树的右节点和左子树的左节点。虽然都是比较两颗树，但本题与26题比较树的子结构有些区别。

public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
         if (pRoot == null)
            return true;
        return Symmetrical(pRoot.left, pRoot.right);
    }

    boolean Symmetrical(TreeNode t1, TreeNode t2) {
//都为空时，才对称。有一个为空，另一个不为空时，不对称。都不为空，进行值比较，然后递归
        if (t1 == null && t2 == null)
            return true;
        if (t1 == null || t2 == null)
            return false;
        if (t1.val != t2.val)
            return false;
        return Symmetrical(t1.left, t2.right) && Symmetrical(t1.right, t2.left);
    }
}

思路2：非递归写法 深度遍历 使用栈 广度遍历使用队列。这里使用栈

import java.util.Stack;
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
      Stack<TreeNode> stack = new Stack<>();
      if(pRoot == null) return true;
      stack.push(pRoot.left);
      stack.push(pRoot.right);
      while(!stack.empty()){
          TreeNode t1 = stack.pop();
          TreeNode t2 = stack.pop();
          if (t1 == null && t2 == null) //都为空需要进一步判断，这与递归不同
//这是因为有可能是某个节点的左子树都是空，但是还需要比较这个节点的右子树
//所以冒然判断两个节点为空，就说是对称的是不行的，需要继续判断。
            continue;
          if (t1 == null || t2 == null)
            return false;
          if (t1.val != t2.val)
            return false;
          stack.push(t1.right);
          stack.push(t2.left);
          stack.push(t1.left);
          stack.push(t2.right);
      }
      return true;
    }
}

所以补充队列的写法

import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
      if(pRoot == null) return true;
      Queue<TreeNode> queue = new LinkedList<>();
      queue.offer(pRoot.left);
      queue.offer(pRoot.right);
      while(!queue.isEmpty()){
          TreeNode t1 = queue.poll();
          TreeNode t2 = queue.poll();
          if (t1 == null && t2 == null)
            continue;
          if (t1 == null || t2 == null)
            return false;
          if (t1.val != t2.val)
            return false;
          queue.offer(t1.left);
          queue.offer(t2.right);
          queue.offer(t1.right);
          queue.offer(t2.left);

      }
      return true;
    }
}