-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSameTree_100.java
More file actions
85 lines (78 loc) · 2.47 KB
/
Copy pathSameTree_100.java
File metadata and controls
85 lines (78 loc) · 2.47 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package com.leetcode.tree;
import java.util.Stack;
/**
* Created by charles on 3/28/17.
* Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value
*/
public class SameTree_100 {
/**
* Recursion, isSame(p.left, q.left) && isSame(p.right, q.right)
*/
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null) {
return false;
}
if (q == null) {
return false;
}
if (p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)) {
return true;
}
return false;
}
/** simplified recursion version */
public boolean isSameTreeIII(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return p.val == q.val && isSameTreeIII(p.left, q.left) && isSameTreeIII(p.right, q.right);
}
/** Iteration solution */
public boolean isSameTreeII(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(p);
stack2.push(q);
TreeNode p1 = null;
TreeNode p2 = null;
while (!stack1.isEmpty() && !stack2.isEmpty()) {
p1 = stack1.pop();
p2 = stack2.pop();
if (p1.val != p2.val) {
return false;
}
// structure different
if (p1.left == null && p2.left != null) {
return false;
} else if (p1.left != null && p2.left == null) {
return false;
} else if (p1.right == null && p2.right != null) {
return false;
} else if (p1.right != null && p2.right == null) {
return false;
}
if (p1.left != null && p2.left != null) {
stack1.push(p1.left);
stack2.push(p2.left);
}
if (p1.right != null && p2.right != null) {
stack1.push(p1.right);
stack2.push(p2.right);
}
}
return true;
}
}