leetcode 653. Two Sum IV - Input is a BST 中序遍历 + 深度优先遍历DFS

墨蓝 2022-06-03 05:40 109阅读 0赞

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:  
Input:  
5  
/ \\  
3 6  
/ \\ \\  
2 4 7

Target = 9

Output: True  
Example 2:  
Input:  
5  
/ \\  
3 6  
/ \\ \\  
2 4 7

Target = 28

Output: False

本题题意很简单，直接做一个中序遍历，存储到set中，然后做一次查询即可

这个是必须要注意的：**注意set做查询的时候要把当前元素删除，然后查询之后再插入**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    /*
    struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution
    {
    public:
        set<int> all;
        bool findTarget(TreeNode* root, int k) 
        {
            dfs(root);
            for (auto i : all)
            {
                all.erase(i);
                if (all.find(k - i) != all.end())
                    return true;
                all.insert(i);
            }
            return false;
        }
    
        void dfs(TreeNode* root)
        {
            if (root == NULL)
                return;
            else
            {
                dfs(root->left);
                all.insert(root->val);
                dfs(root->right);
            }
        }
    };