描述
例如： 下面这棵二叉树是对称的
下面这棵二叉树不对称。
数据范围：节点数满足 0 le n le 10000≤n≤1000，节点上的值满足 |val| le 1000∣val∣≤1000
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
备注：
你可以用递归和迭代两种方法解决这个问题
示例1
输入：{1,2,2,3,4,4,3}
返回值：true
示例2
输入：{8,6,9,5,7,7,5}
返回值：false
第一种解法
直接将树分为左子树 和 右子树java二叉树算法java二叉树算法，然后循环遍历，判断对应节点是否一致即可，代码如下
public boolean firstIsSymmetrical(TreeNode pRoot) {
if(pRoot == null){
return true;
}
if(pRoot.left == null && pRoot.right == null){
return true;
}
<p>
if(pRoot.left == null || pRoot.right == null){
return false;
}
return isSame(pRoot.left,pRoot.right);
}
public boolean isSame(TreeNode leftTree, TreeNode rightTree){
if(leftTree == null && rightTree == null){
return true;
}
if(leftTree != null && rightTree != null && leftTree.val == rightTree.val){
return isSame(leftTree.left,rightTree.right) && isSame(leftTree.right,rightTree.left);
  ![二叉树的递归遍历算法_java二叉树算法_java二叉树的遍历算法][4]
}
return false;</p>
第二种解法
其实和第一种解法类似，但是不采用递归的方法，使用队列来实现java二叉树算法 剑指Offer（五十八）：对称的二叉树（Java版），代码如下
public boolean secondIsSymmetrical(TreeNode pRoot) {
if(pRoot == null){
return true;
}
if(pRoot.left == null && pRoot.right == null){
return true;
}
<p>![二叉树的递归遍历算法_java二叉树算法_java二叉树的遍历算法][5]
if(pRoot.left == null || pRoot.right == null){
return false;
}
Queue leftTree = new LinkedList();
Queue rightTree = new LinkedList();
leftTree.add(pRoot.left);
rightTree.add(pRoot.right);
while (!leftTree.isEmpty() && !rightTree.isEmpty()){
TreeNode left = leftTree.poll();
TreeNode right = rightTree.poll();
if(left == null && right == null){
continue;
}
  ![java二叉树的遍历算法_二叉树的递归遍历算法_java二叉树算法][6]
if(left == null || right == null){
return false;
}
if(left.val != right.val){
return false;
}
leftTree.add(left.left);
leftTree.add(left.right);
rightTree.add(right.right);
rightTree.add(right.left);
}
return leftTree.isEmpty() && rightTree.isEmpty();