All Elements in Two Binary Search Trees
给两个bst, 返回一个sorted list. 我直接用merge list做的, 反正复杂度都一样.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
List<Integer> l1 = new ArrayList<>();
List<Integer> l2 = new ArrayList<>();
get(root1, l1);
get(root2, l2);
return merge(l1, l2);
}
private void get(TreeNode t, List<Integer> l) {
if(t == null)
return;
get(t.left, l);
l.add(t.val);
get(t.right, l);
}
private List<Integer> merge(List<Integer> l1, List<Integer> l2) {
int i = 0;
int j = 0;
List<Integer> res = new ArrayList<>();
while(i < l1.size() && j < l2.size()) {
if(l1.get(i) <= l2.get(j)) {
res.add(l1.get(i++));
}
else {
res.add(l2.get(j++));
}
}
while(i < l1.size()) {
res.add(l1.get(i++));
}
while(j < l2.size()) {
res.add(l2.get(j++));
}
return res;
}
}