653.Two Sum IV - Input is a BST

653.Two Sum IV - Input is a BST

难度:Easy

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

案例 1:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
输出: True
案例 2:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 28
输出: False

先序遍历,得到有序数组,然后寻找满足条件的即可。

/**
* 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 {
vector<int> target;
void initial(TreeNode* root)
{
if(!root) return;
if(root->left) initial(root->left);
target.push_back(root->val);
if(root->right) initial(root->right);
}
public:
bool findTarget(TreeNode* root, int k) {
initial(root);
int first=0;
int last=target.size()-1;
while(first<last)
{
int t=target[first]+target[last];
if(t==k) return true;
else if(t>k) last--;
else first++;
}
return false;
}
};

也可使用map来判断两数之和,通过空间复杂度换取时间复杂度。

执行用时 : 76 ms, 在Two Sum IV - Input is a BST的C++提交中击败了60.15% 的用户 内存消耗 : 25 MB, 在Two Sum IV - Input is a BST的C++提交中击败了83.87% 的用户