请实现⼀个函数，⽤来判断⼀棵⼆叉树是不是对称的。注意，如果⼀个⼆叉树同此⼆叉树的镜像是同样
的，定义其为对称的。
例如：下⾯这棵⼆叉树是对称的
下⾯这个就不是对称的：
示例1
输⼊：{8,6,6,5,7,7,5}
返回值：true
示例2：
输⼊：{8,6,9,5,7,7,5}
返回值：false
思路及解答
递归
递归，先判断根节点是否为空，不为空则判断左右⼦树是不是对称。
如果左右⼦树都为空，则返回 true ，如果有⼀个为空，则返回 false ，如果两个都不为空的时候，除了对⽐左右两个节点的值，还需要递归，对⽐左⼦树的左⼦树和右⼦树的右⼦树是否相等，左⼦树的右⼦树和右⼦树的左⼦树是否相等。
java
public class Solution { public boolean jude(TreeNode left, TreeNode right) { // 如果左右两个都为空，则对称 if (left == null && right == null) { return true; } else if (left == null || right == null) { // 如果左右两个有⼀个为空，那么就不对称 return false; } // 都不为空的情况，需要判断两个的值，是不是相等 if (left.val != right.val) { return false; } else { // 递归判断，左⼦树的左⼦树和右⼦树的右⼦树，左⼦树的右⼦树和右⼦树的左⼦树 return jude(left.left, right.right) && jude(left.right, right.left); } } public boolean isSymmetrical(TreeNode pRoot) { // 判断根节点是否为空，如果不为空则判断左右⼦树 return pRoot==null || jude(pRoot.left, pRoot.right); } }- 时间复杂度：O(n)
- 空间复杂度：O(n),最坏情况下，⼆叉树退化为链表
迭代
是借助两个队列，按照层次，⼀个是按照从左到右添加元素，另外⼀个队列
是按照从右到左添加元素，挨个取出来，进⾏对⽐，不等则说明不对称，如果相等，则再把其左右⼦树
分别按照不同的顺序添加到队列中。代码如下
java
public class Solution { /** * 迭代法 * 使用双端队列，相当于两个栈 */ public boolean isSymmetric2(TreeNode root) { Deque<TreeNode> deque = new LinkedList<>(); deque.offerFirst(root.left); deque.offerLast(root.right); while (!deque.isEmpty()) { TreeNode leftNode = deque.pollFirst(); TreeNode rightNode = deque.pollLast(); if (leftNode == null && rightNode == null) { continue; } if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) { return false; } deque.offerFirst(leftNode.left); deque.offerFirst(leftNode.right); deque.offerLast(rightNode.right); deque.offerLast(rightNode.left); } return true; } /** * 迭代法 * 使用普通队列 */ public boolean isSymmetric3(TreeNode root) { Queue<TreeNode> deque = new LinkedList<>(); deque.offer(root.left); deque.offer(root.right); while (!deque.isEmpty()) { TreeNode leftNode = deque.poll(); TreeNode rightNode = deque.poll(); if (leftNode == null && rightNode == null) { continue; } if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) { return false; } // 这里顺序与使用Deque不同 deque.offer(leftNode.left); deque.offer(rightNode.right); deque.offer(leftNode.right); deque.offer(rightNode.left); } return true;
