653. Two Sum IV - Input is a BST

653. Two Sum IV - Input is a BST (Easy)

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

Companies:
Amazon, Google

Related Topics:
Tree

Similar Questions:

• Two Sum (Easy)
• Two Sum II - Input array is sorted (Easy)
• Two Sum III - Data structure design (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
private:
    vector<int> v;
    void inorder(TreeNode *root) {
        if (!root) return;
        inorder(root->left);
        v.push_back(root->val);
        inorder(root->right);
    }
public:
    bool findTarget(TreeNode* root, int k) {
        inorder(root);
        int i = 0, j = v.size() - 1;
        while (i < j) {
            int sum = v[i] + v[j];
            if (sum == k) return true;
            if (sum > k) --j;
            else ++i;
        }
        return false;
    }
};