Leetcode 1214. 查找两棵二叉搜索树之和（DAY 179）---- 二分查找学习期

我就是我 2022-09-14 02:16 56阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷自解） ##

--------------------

/** * 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 visit(vector<int>& v1,TreeNode* root)
        {   
            if(!root)   return;
            visit(v1,root->left);
            v1.emplace_back(root->val);
            visit(v1,root->right);
        }
    
        bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) { 
            vector<int> v1,v2;
            visit(v1,root1);
            visit(v2,root2);
    
            int left = 0,pos = v2.size();
            while(left < v1.size())
            { 
                auto iter = lower_bound(v2.begin(),v2.begin()+pos,target-v1[left]);
                ++left;
                if(iter == v2.end())    continue;
                if(*iter == target-v1[left-1])    return true;
                pos = iter - v2.begin();
            }
            return false;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/0e6ef24131f14f7799ecebffd6cbd12f.png