2022/01/26 - 1305. All Elements in Two Binary Search Trees
1305. All Elements in Two Binary Search Trees - Hard
Description
1305. All Elements in Two Binary Search Trees
Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order.
就是将两个二叉搜索树中的元素合并到一个list中并且按照升序排序。首先我能想到的就是用中序遍历将两个二叉搜索树升序放入数组中，然后再合并两个数组。
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 | /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
// use inorder to generate sorted list for each TreeNode
List<Integer> tree1 = new ArrayList();
inorder(root1, tree1);
List<Integer> tree2 = new ArrayList();
inorder(root2, tree2);
int n1 = tree1.size(), n2 = tree2.size();
// merge two lists
List<Integer> ans = new ArrayList<>();
for (int i = 0, j = 0; i < n1 || j < n2;) {
if (i < n1 && j < n2) {
if (tree1.get(i) < tree2.get(j)) {
ans.add(tree1.get(i++));
} else {
ans.add(tree2.get(j++));
}
} else if (i >= n1) {
ans.add(tree2.get(j++));
} else {
ans.add(tree1.get(i++));
}
}
return ans;
}
private void inorder(TreeNode node, List<Integer> list) {
if (node == null) return;
inorder(node.left, list);
list.add(node.val);
inorder(node.right, list);
}
}
|