对称的二叉树,Java

1、最开始想到的就是二叉树的遍历，使用中序遍历的话，就是左中右，右中左这两种方式进行遍历，之后比较这两个字符串是否相同就可以了

 1 package example;
 2 
 3 public class isSymmetrical {
 4     public class TreeNode {
 5         int val = 0;
 6         TreeNode left = null;
 7         TreeNode right = null;
 8 
 9         public TreeNode(int val) {
10             this.val = val;
11 
12         }
13         
14 
15     }
16     String mOutput(TreeNode root) {
17         StringBuilder sb = new StringBuilder();
18         if (root != null) {
19             sb.append(mOutput(root.left));
20             sb.append(root.val);
21             sb.append(mOutput(root.right));
22         } else {
23             return "";
24         }
25         return sb.toString();
26     }
27     String fMOutput(TreeNode root) {
28         StringBuilder sb = new StringBuilder();
29         if (root != null) {
30             sb.append(mOutput(root.right));
31             sb.append(root.val);
32             sb.append(mOutput(root.left));
33         }
34         return sb.toString();
35     } 
36     boolean isSymmetrical(TreeNode pRoot)
37     {
38         if (pRoot == null) {
39             return true;
40         }
41         String str1 = mOutput(pRoot.left);
42         String str2 = fMOutput(pRoot.right);
43         if (str1.equals(str2)) {
44             return true;
45         }
46         return false;
47     }
48     /**
49      * @param args
50      */
51     public static void main(String[] args) {
52         // TODO Auto-generated method stub
53         
54     }
55 
56 }

但是这种方式不能通过所有的样例，暂时还不知道这种方式的问题所在。

这种方式效率也有点差，因为最优，最差的时间性能都是O(n)，所有的节点都需要遍历，并且都要存起来

2、还可以使用递归的方式，每一次都只是遍历一个点，比较两个点是否相等

 1     boolean isSymetrical(TreeNode pRoot1, TreeNode pRoot2) {
 2         if (pRoot1 == null && pRoot2 == null) {
 3             return true;
 4         }
 5         if (pRoot1 == null || pRoot2 == null) {
 6             return false;
 7         }
 8         if (pRoot1.val != pRoot2.val) {
 9             return false;
10         }
11         return (isSymetrical(pRoot1.left, pRoot2.right) && isSymetrical(pRoot1.right, pRoot2.left));
12     }
13     boolean isSymmetrical(TreeNode pRoot)
14     {
15         if (pRoot == null) {
16             return true;
17         }
18         return isSymetrical(pRoot.left, pRoot.right);
19     }

这种方式可以理解为之前的两种不同的中序遍历的方式，只是每次都进行了是否节点相等的判断

也可以理解为左子树的左子节点要和右子树的右子节点相等。左子树的右子节点要和右子树的左子节点相等