Leaf-Similar Trees
判断树底是否相同
my solution
这是一道很简单的题, 实现并不难, 问题是怎么更好地实现.
深度/广度都无法做到”一触即发”(协程/多线程或许可以). 所需需要手动来记录一下.
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
| class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
array<TreeNode*, 200> t1 { root1 };
array<TreeNode*, 200> t2 { root2 };
int i1 = 0, i2 = 0;
while (true) {
while (true) {
if (root1->left) {
root1 = root1->left;
} else if (root1->right) {
root1 = root1->right;
} else {
break;
}
t1[++i1] = root1;
}
while (true) {
if (root2->left) {
root2 = root2->left;
} else if (root2->right) {
root2 = root2->right;
} else {
break;
}
t2[++i2] = root2;
}
if (t1[i1]->val != t2[i2]->val) {
return false;
}
while (i1 > 0) {
if (t1[i1] != t1[i1 - 1]->right && t1[i1 - 1]->right) {
break;
}
--i1;
}
while (i2 > 0) {
if (t2[i2] != t2[i2 - 1]->right && t2[i2 - 1]->right) {
break;
}
--i2;
}
if (!(i1 || i2)) {
break;
} else if (!(i1 && i2)) {
return false;
}
root1 = t1[--i1]->right;
t1[++i1] = root1;
root2 = t2[--i2]->right;
t2[++i2] = root2;
}
return true;
}
};
|
代码量是多了点, 但是没有使用高级数据结构, 没有递归. 能够”一触即发”.