1+ package Algorithms .tree ;
2+
3+ import java .util .Stack ;
4+
5+ /**
6+ * Definition for binary tree
7+ * public class TreeNode {
8+ * int val;
9+ * TreeNode left;
10+ * TreeNode right;
11+ * TreeNode(int x) { val = x; }
12+ * }
13+ */
14+ public class IsSameTree1 {
15+ // solution 1:
16+ public boolean isSameTree1 (TreeNode p ,TreeNode q ) {
17+ if (p ==null &&q ==null ) {
18+ return true ;
19+ }
20+
21+ if (p ==null ||q ==null ) {
22+ return false ;
23+ }
24+
25+ return p .val ==q .val &&
26+ isSameTree (p .left ,q .left ) &&
27+ isSameTree (p .right ,q .right );
28+ }
29+
30+ // Solution 2:
31+ public boolean isSameTree (TreeNode p ,TreeNode q ) {
32+ if (p ==null &&q ==null ) {
33+ return true ;
34+ }
35+
36+ if (p ==null ||q ==null ) {
37+ return false ;
38+ }
39+
40+ Stack <TreeNode >s1 =new Stack <TreeNode >();
41+ Stack <TreeNode >s2 =new Stack <TreeNode >();
42+
43+ s1 .push (p );
44+ s2 .push (q );
45+
46+ while (!s1 .isEmpty () && !s2 .isEmpty ()) {
47+ TreeNode cur1 =s1 .pop ();
48+ TreeNode cur2 =s2 .pop ();
49+
50+ // 弹出的节点的值必须相等
51+ if (cur1 .val !=cur2 .val ) {
52+ return false ;
53+ }
54+
55+ // tree1的right节点，tree2的right节点，可以同时不为空，也可以同时为空，否则返回false.
56+ if (cur1 .left !=null &&cur2 .left !=null ) {
57+ s1 .push (cur1 .left );
58+ s2 .push (cur2 .left );
59+ }else if (!(cur1 .left ==null &&cur2 .left ==null )) {
60+ return false ;
61+ }
62+
63+ // tree1的左节点，tree2的left节点，可以同时不为空，也可以同时为空，否则返回false.
64+ if (cur1 .right !=null &&cur2 .right !=null ) {
65+ s1 .push (cur1 .right );
66+ s2 .push (cur2 .right );
67+ }else if (!(cur1 .right ==null &&cur2 .right ==null )) {
68+ return false ;
69+ }
70+ }
71+
72+ return true ;
73+ }
74+ }