1+ package Algorithms .tree ;
2+
3+ import java .util .Stack ;
4+
5+ public class IsSymmetric {
6+ /**
7+ * Definition for binary tree public class TreeNode { int val; TreeNode
8+ * left; TreeNode right; TreeNode(int x) { val = x; } }
9+ */
10+ // solution 1:
11+ public boolean isSymmetric (TreeNode root ) {
12+ if (root ==null ) {
13+ return true ;
14+ }
15+
16+ return isSymmetricTree (root .left ,root .right );
17+ }
18+
19+ /*
20+ * 判断两个树是否互相镜像 (1) 根必须同时为空，或是同时不为空
21+ *
22+ * 如果根不为空: (1).根的值一样 (2).r1的左树是r2的右树的镜像 (3).r1的右树是r2的左树的镜像
23+ */
24+ public boolean isSymmetricTree1 (TreeNode root1 ,TreeNode root2 ) {
25+ if (root1 ==null &&root2 ==null ) {
26+ return true ;
27+ }
28+
29+ if (root1 ==null ||root2 ==null ) {
30+ return false ;
31+ }
32+
33+ return root1 .val ==root2 .val
34+ &&isSymmetricTree (root1 .left ,root2 .right )
35+ &&isSymmetricTree (root1 .right ,root2 .left );
36+ }
37+
38+ // solution 2:
39+ public boolean isSymmetricTree (TreeNode root1 ,TreeNode root2 ) {
40+ if (root1 ==null &&root2 ==null ) {
41+ return true ;
42+ }
43+
44+ if (root1 ==null ||root2 ==null ) {
45+ return false ;
46+ }
47+
48+ Stack <TreeNode >s1 =new Stack <TreeNode >();
49+ Stack <TreeNode >s2 =new Stack <TreeNode >();
50+
51+ // 一定记得初始化
52+ s1 .push (root1 );
53+ s2 .push (root2 );
54+
55+ while (!s1 .isEmpty () && !s2 .isEmpty ()) {
56+ TreeNode cur1 =s1 .pop ();
57+ TreeNode cur2 =s2 .pop ();
58+
59+ if (cur1 .val !=cur2 .val ) {
60+ return false ;
61+ }
62+
63+ if (cur1 .left !=null &&cur2 .right !=null ) {
64+ s1 .push (cur1 .left );
65+ s2 .push (cur2 .right );
66+ }else if (!(cur1 .left ==null &&cur2 .right ==null )) {
67+ return false ;
68+ }
69+
70+ if (cur1 .right !=null &&cur2 .left !=null ) {
71+ s1 .push (cur1 .right );
72+ s2 .push (cur2 .left );
73+ }else if (!(cur1 .right ==null &&cur2 .left ==null )) {
74+ return false ;
75+ }
76+ }
77+
78+ return true ;
79+ }
80+ }