1305.两颗二叉搜索树中的所有元素

题目

两颗二叉搜索树中的所有元素

思路 1

先前序遍历两个二叉搜索树，将所有节点的值存放至vector<int>中，然后在进行排序。

思路 2

先进行中序遍历，得到两个二叉搜索树对应的数组，该数组均为有序（从小到大），然后进行归并即可。

题解

• 题解 1
• 题解 2

/**
 * 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:
    vector<int> res;
    // 二叉树的前序遍历
    void preTraverse(TreeNode* root) {
        if(root == nullptr) return;
        res.push_back(root->val);
        preTraverse(root->left);
        preTraverse(root->right);
    }
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        preTraverse(root1);
        preTraverse(root2);
        sort(res.begin(), res.end());
        return res;
    }
};

• 时间复杂度：O((n + m) \ log(n + m))，其中 n 和 m* 分别为两棵二叉搜索树的节点个数。
• 空间复杂度：O(n + m)

执行用时：120 ms, 在所有 C++ 提交中击败了82.38%的用户

内存消耗：83.3 MB, 在所有 C++ 提交中击败了60.43%的用户

通过测试用例：48 / 48

/**
 * 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:
    vector<int> res;
    // 中序遍历
    void InoTraversal(TreeNode* root, vector<int>& nums){
        if(root == nullptr) return;
        InoTraversal(root->left, nums);
        nums.push_back(root->val);
        InoTraversal(root->right, nums);       
    }
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> nums1, nums2;
        InoTraversal(root1, nums1);
        InoTraversal(root2, nums2);

        int i = 0, j = 0;
        while(i < nums1.size() && j < nums2.size()){
            if(nums1[i] < nums2[j])
                res.push_back(nums1[i++]);
            else
                res.push_back(nums2[j++]);
        }
        while(i < nums1.size()) res.push_back(nums1[i++]);
        while(j < nums2.size()) res.push_back(nums2[j++]);

        return res;
    }
};

• 时间复杂度：O((n + m))，其中 n 和 m 分别为两棵二叉搜索树的节点个数。
• 空间复杂度：O(n + m)

执行用时：116 ms, 在所有 C++ 提交中击败了88.62%的用户

内存消耗：85.4 MB, 在所有 C++ 提交中击败了6.23%的用户

通过测试用例：48 / 48