Powered By GitBook
653.Two Sum IV - Input is a BST

653.Two Sum IV - Input is a BST

难度:Easy
给定一个二叉搜索树和一个目标结果,如果 BST 中存在两个元素且它们的和等于给定的目标结果,则返回 true。
1
案例 1:
2
3
输入:
4
5
5
/ \
6
3 6
7
/ \ \
8
2 4 7
9
10
Target = 9
11
12
输出: True
13
14
15
案例 2:
16
17
输入:
18
5
19
/ \
20
3 6
21
/ \ \
22
2 4 7
23
24
Target = 28
25
26
输出: False
Copied!
先序遍历,得到有序数组,然后寻找满足条件的即可。
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
vector<int> target;
12
void initial(TreeNode* root)
13
{
14
if(!root) return;
15
if(root->left) initial(root->left);
16
target.push_back(root->val);
17
if(root->right) initial(root->right);
18
19
20
}
21
22
public:
23
bool findTarget(TreeNode* root, int k) {
24
25
initial(root);
26
int first=0;
27
int last=target.size()-1;
28
while(first<last)
29
{
30
int t=target[first]+target[last];
31
if(t==k) return true;
32
else if(t>k) last--;
33
else first++;
34
}
35
return false;
36
}
37
};
Copied!
也可使用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% 的用户
Last modified 2yr ago
Copy link