剑指offer-58、对称二叉树

题⽬形貌

请实现⼀个函数，⽤来判定⼀棵⼆叉树是不是对称的。注意，假如⼀个⼆叉树同此⼆叉树的镜像是同样
的，界说其为对称的。
比方：下⾯这棵⼆叉树是对称的

下⾯这个就不是对称的：

示例1
输⼊：{8,6,6,5,7,7,5}
返回值：true
示例2：
输⼊：{8,6,9,5,7,7,5}
返回值：false
思绪及解答

递归

递归，先判定根节点是否为空，不为空则判定左右⼦树是不是对称。
假如左右⼦树都为空，则返回 true ，假如有⼀个为空，则返回 false ，假如两个都不为空的时间，除了对⽐左右两个节点的值，还须要递归，对⽐左⼦树的左⼦树和右⼦树的右⼦树是否相称，左⼦树的右⼦树和右⼦树的左⼦树是否相称。

1. public class Solution {
2.     public boolean jude(TreeNode left, TreeNode right) {
3.         // 如果左右两个都为空，则对称
4.         if (left == null && right == null) {
5.                 return true;
6.         } else if (left == null || right == null) {
7.             // 如果左右两个有⼀个为空，那么就不对称
8.             return false;
9.         }
10.         
11.         // 都不为空的情况，需要判断两个的值，是不是相等
12.         if (left.val != right.val) {
13.                 return false;
14.         } else {
15.             // 递归判断，左⼦树的左⼦树和右⼦树的右⼦树，左⼦树的右⼦树和右⼦树的左⼦树
16.             return jude(left.left, right.right) && jude(left.right, right.left);
17.         }
18.     }
19.    
20.     public boolean isSymmetrical(TreeNode pRoot) {
21.         // 判断根节点是否为空，如果不为空则判断左右⼦树
22.         return pRoot==null || jude(pRoot.left, pRoot.right);
23.     }
24. }

复制代码

• 时间复杂度：O(n)
  
• 空间复杂度：O(n),最坏环境下，⼆叉树退化为链表
  

迭代

是借助两个队列，按照条理，⼀个是按照从左到右添加元素，别的⼀个队列
是按照从右到左添加元素，挨个取出来，进⾏对⽐，不等则分析不对称，假如相称，则再把其左右⼦树
分别按照差别的次序添加到队列中。代码如下

1. public class Solution {
2.     /**
3.     * 迭代法
4.      * 使用双端队列，相当于两个栈
5.      */
6.     public boolean isSymmetric2(TreeNode root) {
7.         Deque<TreeNode> deque = new LinkedList<>();
8.         deque.offerFirst(root.left);
9.         deque.offerLast(root.right);
10.         while (!deque.isEmpty()) {
11.             TreeNode leftNode = deque.pollFirst();
12.             TreeNode rightNode = deque.pollLast();
13.             if (leftNode == null && rightNode == null) {
14.                 continue;
15.             }
17.             if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
18.                 return false;
19.             }
20.             deque.offerFirst(leftNode.left);
21.             deque.offerFirst(leftNode.right);
22.             deque.offerLast(rightNode.right);
23.             deque.offerLast(rightNode.left);
24.         }
25.         return true;
26.     }
28.     /**
29.      * 迭代法
30.      * 使用普通队列
31.      */
32.     public boolean isSymmetric3(TreeNode root) {
33.         Queue<TreeNode> deque = new LinkedList<>();
34.         deque.offer(root.left);
35.         deque.offer(root.right);
36.         while (!deque.isEmpty()) {
37.             TreeNode leftNode = deque.poll();
38.             TreeNode rightNode = deque.poll();
39.             if (leftNode == null && rightNode == null) {
40.                 continue;
41.             }
43.             if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
44.                 return false;
45.             }
46.             // 这里顺序与使用Deque不同
47.             deque.offer(leftNode.left);
48.             deque.offer(rightNode.right);
49.             deque.offer(leftNode.right);
50.             deque.offer(rightNode.left);
51.         }
52.         return true;
53.     }
54. }

复制代码

• 空间复杂度为 O(n)
  
• 时间复杂度为 O(n) ,每个节点只会⼊队出队⼀次。