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

题目：

思路：

二叉搜索树，还升序，自然是中序遍历了。然后就是要考虑一个归并排序的问题，我查了一下归并排序感觉并不是网上说的那种，我这种就是一一对比，通过递归实现。

整体就是通过两个数组存放中序遍历后的两颗二叉搜索树，然后归并排序。

代码：

class Solution {
public:
    void dfs(TreeNode* node, vector<int>& v){
        if(! node){
            return;
        }
        // 中序遍历
        dfs(node->left, v);
        v.push_back(node->val);
        dfs(node->right, v);
    }

    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> v1, v2;
        dfs(root1, v1);
        dfs(root2, v2);

        vector<int> ans;
        int i = 0, j = 0;
        // 归并排序
        while(i < v1.size() || j < v2.size()){
            // v1还有剩余，同时v1[i] <= v2[j] 或者v2没剩余了，直接push v1
            if(i < v1.size() && (j == v2.size() || v1[i] <= v2[j])){
                ans.push_back(v1[i++]);
            }else{
                ans.push_back(v2[j++]);
            }
        }
        return ans;
    }
};

Rank：

Tips：

太困了，感觉用时上已经没啥优化了，内存上可以试试不用外部存储或只用一个存储空间，但是太菜了，也没仔细看大神解析，也有点困，明早还要挤地铁，所以有空再看看内存方面的优化，不过感觉会增加一部分的用时。

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

原文：https://www.cnblogs.com/lzyrookie/p/14608726.html