给定一个二叉搜索树和一个目标结果,如果 BST 中存在两个元素且它们的和等于给定的目标结果,则返回 true。
案例 1:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
输出: True
案例 2:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 28
输出: False
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
相关参考:LeetCode 173. 二叉搜索树迭代器(中序遍历)
class Solution {
TreeNode *begin, *end, *temp;
stack<TreeNode*> s1, s2;
public:
bool findTarget(TreeNode* root, int k) {
if(root == NULL)
return false;
begin = end = root;
TreeNode *i = next(), *j = prev();
while(i != j)
{
if(i->val+j->val > k)
j = prev();//和大了,j减小
else if(i->val+j->val < k)
i = next();//和小了,i增大
else//if(i->val+j->val == k)
return true;
}
return false;
}
TreeNode* next()//正向迭代器,从最小的开始
{
while(begin)
{
s1.push(begin);
begin = begin->left;
}
temp = s1.top();
s1.pop();
begin = temp->right;
return temp;
}
TreeNode* prev()//反向迭代器,从最大的开始
{
while(end)
{
s2.push(end);
end = end->right;
}
temp = s2.top();
s2.pop();
end = temp->left;
return temp;
}
};