101.Symmetric Tree

题目链接：https://leetcode.com/problems/symmetric-tree/description/

题目大意：给出一个二叉树，判断其是否是对称的，例子如下

法一：用常规层序遍历一直WA，某一天突然开窍发现bug，改了之后提交ac了，这个bug其实就是怎么去记录当前层的最后一个结点，不能直接用结点指针进行标记，因为有可能出现null的情况，也不能用每层固定的结点个数也就是2^depth来进行判断是否是一层的最后一个结点，因为前面可能有很多个null，而并不是每个null都会进入队列。这里采用的办法是利用queue.size()来记录每层进队列的结点个数，然后利用cnt--操作来判断当前层是否遍历完。虽然时间长点，但毕竟自己的心血，代码如下（耗时5ms）：

 1     public static boolean isSymmetric(TreeNode root) {
 2         if(root == null) {
 3             return true;
 4         }
 5         boolean flag = true;
 6         Queue<TreeNode> queue = new LinkedList<TreeNode>();
 7         queue.offer(root);
 8         int cnt = 1;
 9         List<TreeNode> listNode = new ArrayList<TreeNode>();
10         while(!queue.isEmpty()) {
11             TreeNode node = queue.poll();
12             cnt--;
13             listNode.add(node);
14             if(node != null) {
15                 queue.offer(node.left);
16                 queue.offer(node.right);
17             }
18             if(cnt == 0) {
19                 cnt = queue.size();
20                 int length = listNode.size();
21                 for(int i = 0; i < length / 2; i++) {
22                     if((listNode.get(i) == null && listNode.get(length - 1 - i) != null) ||
23                         (listNode.get(i) != null && listNode.get(length - 1 - i) == null)) {
24                         flag = false;
25                         break;
26                     }
27                     else if(listNode.get(i) != null && listNode.get(length - 1 - i) != null) {
28                         if(listNode.get(i).val != listNode.get(length - 1 - i).val) {
29                             flag = false;
30                             break;
31                         }
32                     }
33                 }
34                 if(flag == false) {
35                     return flag;
36                 }
37                 listNode.clear();
38             }
39         }
40         return flag;
41     }

View Code

法二（借鉴）：看完题解后，利用层序遍历的变种，每次进队时同时压入左右孩子，注意压入的顺序，代码如下（耗时2ms）：

 1     public static boolean isSymmetric(TreeNode root) {
 2         Queue<TreeNode> queue = new LinkedList<TreeNode>();
 3         queue.offer(root);
 4         queue.offer(root);
 5         boolean flag = true;
 6         while(!queue.isEmpty()) {
 7             TreeNode nodeLeft = queue.poll();
 8             TreeNode nodeRight = queue.poll();
 9             
10             if((nodeLeft != null && nodeRight == null) || (nodeLeft == null && nodeRight != null)) {
11                 return false;
12             }
13             else if(nodeLeft != null && nodeRight != null) {
14                 if(nodeLeft.val != nodeRight.val) {
15                     return false;
16                 }
17                 else {
18                     queue.offer(nodeLeft.left);
19                     queue.offer(nodeRight.right);
20                     
21                     queue.offer(nodeLeft.right);
22                     queue.offer(nodeRight.left);
23                 }
24             }
25         }
26         return flag;
27     }

View Code

法三（借鉴）：利用双端队列来做，思想与法二类似，每次同时压入左右孩子，只是这里用到了java中的双端队列类，代码如下（耗时3ms）：

 1     public static boolean isSymmetric(TreeNode root) {
 2         Deque<TreeNode> queue = new LinkedList<TreeNode>();
 3         queue.offerFirst(root);
 4         queue.offerLast(root);
 5         boolean flag = true;
 6         while(!queue.isEmpty()) {
 7             TreeNode nodeLeft = queue.pollFirst();
 8             TreeNode nodeRight = queue.pollLast();
 9             
10             if((nodeLeft != null && nodeRight == null) || (nodeLeft == null && nodeRight != null)) {
11                 return false;
12             }
13             else if(nodeLeft != null && nodeRight != null) {
14                 if(nodeLeft.val != nodeRight.val) {
15                     return false;
16                 }
17                 else {
18                     queue.offerFirst(nodeLeft.left);
19                     queue.offerFirst(nodeLeft.right);
20                     
21                     queue.offerLast(nodeRight.right);
22                     queue.offerLast(nodeRight.left);
23                 }
24             }
25         }
26         return flag;
27     }

View Code

法四（借鉴）：这个比较难，利用递归左右子树同时判断，代码如下（耗时0ms）：

 1     public static boolean isSymmetric(TreeNode root) {
 2         if(root == null) {
 3             return true;
 4         }
 5         return isSymmetric2(root, root);
 6     }
 7     public static boolean isSymmetric2(TreeNode root1, TreeNode root2) {
 8         if(root1 == null && root2 == null) {
 9             return true;
10         }
11         else if(root1 == null || root2 == null) {
12             return false;
13         }
14         else {
15             if(root1.val != root2.val) {
16                 return false;
17             }
18             else {
19                 return isSymmetric2(root1.left, root2.right) && isSymmetric2(root1.right, root2.left);
20             }
21         }
22     }

View Code