653. 兩數之和 IV - 輸入 BST

1.題目描述

給定一個二叉搜尋樹和一個目标結果，如果 BST 中存在兩個元素且它們的和等于給定的目标結果，則傳回 true。

案例 1:

案例 2:

2.方法1 （中序周遊+二分查找）

中序周遊是遞增序列，在序列中二分查找，這種兩個下标left和right，分别指向序列的頭和尾，如果list[left] + list[right] < target則left++,如果list[left] + list[right] > target則right–,相等傳回true。

3.代碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        if(root == NULL){
            return false;
        }
        vector<int> vec;
        inorder(root,vec);
        int left = 0,right = vec.size() - 1;
        while(left < right){
            int sum = vec[left] + vec[right];
            if(sum == k){
                return true;
            }
            else if(sum < k){
                left++;
            }
            else{
                right--;
            }
        }
        return false;
    }
    void inorder(TreeNode* root, vector<int>& vec){
        if(root == NULL){
            return;
        }
        inorder(root->left,vec);
        vec.push_back(root->val);
        inorder(root->right,vec);
    }
};
           

4.複雜度分析

時間複雜度：O（N）

空間複雜度：O（N）

5.方法2（dfs + set）

深度優先周遊二叉樹，把節點的值儲存到set中，每周遊一個節點就判斷目前k - 目前節點的值是否在set中

6.代碼：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        set<int> s;
        return find(root,k,s);
    }
    bool find(TreeNode* root,int k,set<int>& s){
        if(root == NULL){
            return false;
        }
        if(s.find(k - root->val) != s.end()){
            return true;
        }
        s.insert(root->val);
        return find(root->left,k,s) || find(root->right,k,s);
    }
};
           

7.複雜度分析

時間複雜度：O（N）

空間複雜度：O（N）

9.方法3（bfs+set）

橫向優先搜尋二叉搜尋樹，判斷set中是否存在k-node->val，存在則傳回true，否則把node->val插入set中，如果node的左右子節點不為空，則依次插入隊列中。

10.代碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        if(root == NULL){
            return false;
        }
        queue<TreeNode*> q;
        set<int> s;
        q.push(root);
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            if(s.find(k - node->val) != s.end()){
                return true;
            }
            s.insert(node->val);
            if(node->left){
                q.push(node->left);
            }
            if(node->right){
                q.push(node->right);
            }
        }
        return false;
    }
};
           

11.複雜度分析

時間複雜度：O(n)

空間複雜度：O(n)