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

caution

原题链接：https://leetcode-cn.com/problems/all-elements-in-two-binary-search-trees/

思路

从题目中可以看到，只要对二叉搜索树进行中序遍历就能得到两个有序的集合，然后使用归并的方式将两个集合有顺序地合到一起就解决了本题。

（中序遍历 + 归并）

代码

/**
 * 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> t1, t2, ans;

    void dfs(vector<int> &v, TreeNode* tree) {
        if (tree) {
            dfs(v, tree->left);
            v.push_back(tree->val);
            dfs(v, tree->right);
        }
    }
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        if (root1) {
            dfs(t1, root1->left);
            t1.push_back(root1->val);
            dfs(t1, root1->right);
        }
        if (root2) {
            dfs(t2, root2->left);
            t2.push_back(root2->val);
            dfs(t2, root2->right);
        }

        int i, j;
        for (i = 0, j = 0; i < t1.size() && j < t2.size();) {
            if (t1[i] <= t2[j]) ans.push_back(t1[i++]);
            else ans.push_back(t2[j++]);
        }

        for (; i < t1.size(); i++) ans.push_back(t1[i]);
        for (; j < t2.size(); j++) ans.push_back(t2[j]);

        return ans;
        
    }
};