Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1 / \ 2 2 / \ / \ 3 4 4 3But the following [1,2,2,null,3,null,3] is not:
1 / \ 2 2 \ \ 3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
问题：判断一棵树是否中心对称
思路：递归（1）一棵树中心对称，可以看成两棵树是否对称，即根节点的左右子树为根的树是否镜面
（2）两个树成镜面，root1和root2 那么root1.left.val=root2.right.val并且 root1.right=root2.left
class TreeNode{ int val; TreeNode left; TreeNode right; public TreeNode(int val){ this.val=val; } } public boolean isSymmetric(TreeNode root) { if(root==null) return true; return isMirror(root,root); } public boolean isMirror(TreeNode r1,TreeNode r2){ if(r1==null&&r2==null) return true; if(r1==null||r2==null) return false; return((r1.val==r2.val)&&isMirror(r1.left,r2.right)&&(isMirror(r1.right,r2.left))); }思想2：除了递归可以利用队列迭代方法
（1）对树进行BFT（广度优先搜索）队列Q中下入栈root和root，相当于两棵树
（2）如果队列不空 r1=p.poll() r2=p.poll()，这里要理解队列中相邻两个元素是来自于两棵树向对称的位置
r1和r2值如果相等的话将他们的子树入队，注意顺序是r1.left r2.right r1.right r2.left （这里保证队列弹出的连个元素是对称的位置的）
注意：队列中连个节点如果都为空，只代表这两个节点对称，不代表他们的兄弟节点也对称，所以在r1==r2==null时还要继续判断，后面接continue而不是直接return true
public boolean isSymmetric2(TreeNode root){//迭代 Queue<TreeNode> q=new LinkedList(); q.add(root); q.add(root); while(!q.isEmpty()){ TreeNode r1=q.poll(); TreeNode r2=q.poll(); if(r1==null&&r2==null) continue;//当左右节点均为空时，队列中只带表对称位置的两节点为空 //他们的兄弟节点不一定对称 if(r1==null||r2==null) return false; if(r1.val!=r2.val) return false; q.add(r1.left); q.add(r2.right); q.add(r1.right); q.add(r2.left); } return true; }