All Elements in Two Binary Search Trees（C++两棵二叉搜索树中的所有元素）

怼烎@ 2022-12-31 07:28 125阅读 0赞

解题思路：

（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:
        void inorder(vector<int> &v,TreeNode *root) {
            if(root==NULL) return;
            inorder(v,root->left);
            v.push_back(root->val);
            inorder(v,root->right); 
        }
        
        vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
            vector<int> v1,v2,v;
            inorder(v1,root1);
            inorder(v2,root2);
            
            int i=0,j=0;
            while(i<v1.size() && j<v2.size()) {
                if(v1[i]<v2[j]) {
                    v.push_back(v1[i]);
                    i++;
                } else if(v1[i]>v2[j]) {
                    v.push_back(v2[j]);
                    j++;
                } else {
                    v.push_back(v1[i]);
                    v.push_back(v2[j]);
                    j++;
                    i++;
                }
            }
            
            while(i<v1.size()) {
                v.push_back(v1[i]);
                i++;
            }
            
            while(j<v2.size()) {
                v.push_back(v2[j]);
                j++;
            }
            
            return v;
        }
    };