Given two binary search trees root1
and root2
.
Return a list containing all the integers from both trees sorted in ascending order.
Example 1:
Input: root1 = [2,1,4], root2 = [1,0,3] Output: [0,1,1,2,3,4]
Example 2:
Input: root1 = [0,-10,10], root2 = [5,1,7,0,2] Output: [-10,0,0,1,2,5,7,10]
Example 3:
Input: root1 = [], root2 = [5,1,7,0,2] Output: [0,1,2,5,7]
Example 4:
Input: root1 = [0,-10,10], root2 = [] Output: [-10,0,10]
Example 5:
Input: root1 = [1,null,8], root2 = [8,1] Output: [1,1,8,8]
Constraints:
- Each tree has at most
5000
nodes. - Each node’s value is between
[-10^5, 10^5]
.
Solution: Inorder traversal + Merge Sort
Time complexity: O(t1 + t2)
Space complexity: O(t1 + t2)
C++
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 |
// Author: Huahua class Solution { public: vector<int> getAllElements(TreeNode* root1, TreeNode* root2) { function<void(TreeNode*, vector<int>&)> inorder = [&](TreeNode* root, vector<int>& t) { if (!root) return; inorder(root->left, t); t.push_back(root->val); inorder(root->right, t); }; vector<int> t1; vector<int> t2; inorder(root1, t1); inorder(root2, t2); vector<int> m; int i = 0; int j = 0; while (m.size() != t1.size() + t2.size()) { if (j == t2.size()) m.push_back(t1[i++]); else if (i == t1.size()) m.push_back(t2[j++]); else m.push_back(t1[i] < t2[j] ? t1[i++] : t2[j++]); } return m; } }; |
C++/STL
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: vector<int> getAllElements(TreeNode* root1, TreeNode* root2) { function<void(TreeNode*, vector<int>&)> inorder = [&](TreeNode* root, vector<int>& t) { if (!root) return; inorder(root->left, t); t.push_back(root->val); inorder(root->right, t); }; vector<int> t1; vector<int> t2; inorder(root1, t1); inorder(root2, t2); vector<int> m; std::merge(begin(t1), end(t1), begin(t2), end(t2), back_inserter(m)); return m; } }; |