Last Updated on 2022-01-26 by Clay
題目
Given two binary search treesroot1androot2, 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 = [1,null,8], root2 = [8,1] Output: [1,1,8,8]
Constraints:
- The number of nodes in each tree is in the range
[0, 5000]. -105 <= Node.val <= 105
題目給定兩顆二元搜索樹，我們要返回兩棵樹合併之後排序過的數值。可以參考上方的圖示，或許會比較清楚。
解題思路
我的解法是比較粗暴、比較差的一種。首先建立一個陣列，然後使用 DFS 遍歷兩棵樹並把所有值儲存在陣列中，最後再將陣列做排序。
（註：我有想到另外一種比較優化後的解法...... 但今天實在太累了，不知道改天還有沒有機會補完。）
C++ 範例程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void DFS(TreeNode* root, vector<int>& elements) {
if (root != nullptr) {
elements.push_back(root->val);
DFS(root->left, elements);
DFS(root->right, elements);
}
}
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
vector<int> ans;
DFS(root1, ans);
DFS(root2, ans);
sort(ans.begin(), ans.end());
return ans;
}
};