leetcode链接：1305. 两棵二叉搜索树中的所有元素
题目分析
方案一
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
| class Solution {
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
recursion(root1, list1);
recursion(root2, list2);
List<Integer> result = new ArrayList<>(list1.size() + list2.size());
int index1 = 0, index2 = 0;
for (int i = 0; i < list1.size() + list2.size(); i++) {
if (index1 >= list1.size()) {
result.add(list2.get(index2));
index2++;
} else if (index2 >= list2.size()) {
result.add(list1.get(index1));
index1++;
} else if (list1.get(index1) < list2.get(index2)) {
result.add(list1.get(index1));
index1++;
} else {
result.add(list2.get(index2));
index2++;
}
}
return result;
}
private void recursion(TreeNode root, List<Integer> list) {
if (root == null) return;
recursion(root.left, list);
list.add(root.val);
recursion(root.right, list);
}
}
|
结果
解答成功:
执行耗时:19 ms,击败了33.20% 的Java用户
内存消耗:44.2 MB,击败了39.67% 的Java用户
分析
时间复杂度：
O( 2 * (n + m) )
空间复杂度：
O( 2 * (n + m) )
方案二
官方题解
官方方案与方案一类似
https://leetcode.cn/problems/all-elements-in-two-binary-search-trees/solutions/101793/liang-ke-er-cha-sou-suo-shu-zhong-de-suo-you-yua-3/
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
| class Solution {
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
List<Integer> nums1 = new ArrayList<Integer>();
List<Integer> nums2 = new ArrayList<Integer>();
inorder(root1, nums1);
inorder(root2, nums2);
List<Integer> merged = new ArrayList<Integer>();
int p1 = 0, p2 = 0;
while (true) {
if (p1 == nums1.size()) {
merged.addAll(nums2.subList(p2, nums2.size()));
break;
}
if (p2 == nums2.size()) {
merged.addAll(nums1.subList(p1, nums1.size()));
break;
}
if (nums1.get(p1) < nums2.get(p2)) {
merged.add(nums1.get(p1++));
} else {
merged.add(nums2.get(p2++));
}
}
return merged;
}
public void inorder(TreeNode node, List<Integer> res) {
if (node != null) {
inorder(node.left, res);
res.add(node.val);
inorder(node.right, res);
}
}
}
作者：力扣官方题解
链接：https:
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|
