LeetCode: 1305-All Elements in Two Binary Search Trees 解題紀錄

Last Updated on 2022-01-26 by Clay

題目

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 = [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;
    }
};

---

References

• https://leetcode.com/problems/all-elements-in-two-binary-search-trees/submissions/

---

Read More

• LeetCode 解題紀錄目錄