題目： LeetCode - 1305. All Elements in Two Binary Search Trees

題目說明

給兩個 Binary Search Tree，回傳一個包含兩個樹的所有值並且以小到大排序後的陣列。

解題思路

由於 BST 的特性，我們可以先取 root 的左子樹，再取 root->val，最後取 root 的右子樹即可得到一個含有 BST 的所有值並排序後的陣列。對於本題來說，我們先取得兩個排序後的陣列，最後使用 Merge Sort 將兩個陣列合併即可得到最後的陣列。

參考解法

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
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2)
    {
        vector<int> t1, t2, v;
        getEle(t1, root1), getEle(t2, root2);
        return merge(t1, t2);
    }

private:
    void getEle(vector<int>& v, TreeNode* root)
    {
        if(!root) return;
        getEle(v, root->left);
        v.emplace_back(root->val);
        getEle(v, root->right);
    }
    
    vector<int> merge(vector<int>& v1, vector<int>& v2)
    {
        int n1 = v1.size(), n2 = v2.size();
        vector<int> v(n1 + n2);
        int i = 0, i1 = 0, i2 = 0;
        while(i1 < n1 || i2 < n2)
        {
            if(i1 >= n1) v[i++] = v2[i2++];
            else if(i2 >= n2) v[i++] = v1[i1++];
            else v[i++] = v1[i1] < v2[i2] ? v1[i1++] : v2[i2++];
        }
        return v;
    }
};