All Elements in Two Binary Search Trees
给两个bst, 返回一个sorted list. 我直接用merge list做的, 反正复杂度都一样.
|
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 |
/** * 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; } } |