[每日 LeetCode] 653. Two Sum IV - Input is a BST

原文链接 [每日 LeetCode] 653. Two Sum IV - Input is a BST

Description:

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

思路：本题要求二叉搜索树下的两数之和。还是采用转化的策略，把树中的元素转化为数组求解。这里有一个特殊之处，二叉搜索树的中序遍历结果肯定是从小到大有序的，有序数组可使用双指针法查找是否存在两数之和。

C++ 代码

/**
 * 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) {
        vector<int> vec;
        inorder(root,vec);
        for(int i=0, j=vec.size()-1; i<j;){
            if (vec[i] + vec[j] == k)
                return true;
            (vec[i] + vec[j] < k) ? ++i: --j;
        }
        return false;
    }
    void inorder(TreeNode* root, vector<int> & vec)
    {
        if(!root)    
            return ;
        inorder(root->left,vec);
        vec.push_back(root->val);
        inorder(root->right,vec);
    } 
};

运行时间：44ms

运行内存：25.1M