Leetcode 653. 两数之和 IV - 输入 BST

题目

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

案例 1:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

输出: True

案例 2:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

输出: False

解题思路

首先中序遍历获得顺序数组，然后遍历每一个元素，再用二分搜索方法找出和为目标值的元素。

C++代码

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
   int binarySearch(vector<int> & elements, int target, int from, int to) {
       if (from > to) return -1;
       int mid = (from + to) / 2;
       if (elements[mid] == target) return mid;
       else if (elements[mid] < target) {
           return binarySearch(elements, target, mid + 1, to);
       } else {
           return binarySearch(elements, target, from, mid - 1);
       }
       return -1;
   }
   bool findTarget(TreeNode* root, int k) {
       vector<int>  elements;
       inorder(root, elements);
       int size = (int)elements.size();
       for (int i = 0; i < size; i++) {
           int target = k - elements[i];
           int index = binarySearch(elements, target, i + 1, size - 1);
           if (index != -1) return true;
       }
       return false;
   }
   void inorder(TreeNode* root, vector<int> & elements) {
       if (root == NULL) return;
       if (root->left) inorder(root->left, elements);
       elements.push_back(root->val);
       if (root->right) inorder(root->right, elements);
   }
};
int main(int argc, const char * argv[]) {
   // insert code here...
   Solution solution;
   TreeNode * node = new TreeNode(5);
   node->left = new TreeNode(3);
   node->right = new TreeNode(6);
   node->left->right = new TreeNode(2);
   node->left->right = new TreeNode(4);
   node->right = new TreeNode(7);
   cout << solution.findTarget(node, 28) << endl;
   return 0;
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst