LeetCode 653. 两数之和 IV - 输入 BST（二叉搜索树迭代器&双指针）

Michael阿明

发布于 2020-07-13 16:00:58

3040

发布于 2020-07-13 16:00:58

1. 题目

给定一个二叉搜索树和一个目标结果，如果 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

创建二叉搜索树的正向和反向迭代器（中序是排好序的），一个从前面开始，一个从后面开始
双指针逼近给定的数即可

相关参考：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;
    }
};