给出两棵二叉搜索树,请你从两棵树中各找出一个节点,使得这两个节点的值之和等于目标值 Target。
如果可以找到返回 True,否则返回 False。
示例 1:
输入:root1 = [2,1,4], root2 = [1,0,3], target = 5
输出:true
解释:2 加 3 和为 5 。
示例 2:
输入:root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
输出:false
提示:
每棵树上最多有 5000 个节点。
-10^9 <= target, node.val <= 10^9
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/two-sum-bsts 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class bst_iter
{
stack<TreeNode*> s;
TreeNode* cur;
int v;
bool postorder;
public:
bst_iter(TreeNode* root, bool postorder = false)
{
cur = root;
this->postorder = postorder;//降序
}
int next()
{
if(!postorder && (cur || !s.empty()))
{
while(cur)
{
s.push(cur);
cur = cur->left;
}
v = s.top()->val;
cur = s.top()->right;
s.pop();
return v;
}
else if(postorder && (cur || !s.empty()))
{
while(cur)
{
s.push(cur);
cur = cur->right;//降序先遍历右边
}
v = s.top()->val;
cur = s.top()->left;
s.pop();
return v;
}
return INT_MAX;
}
};
class Solution {
public:
bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
bst_iter bstit1(root1);//ascending
bst_iter bstit2(root2,true);//descending
int v1 = bstit1.next(), v2 = bstit2.next();
while(v1 != INT_MAX && v2 != INT_MAX)
{
if(v1+v2 < target)
v1 = bstit1.next();
else if(v1+v2 > target)
v2 = bstit2.next();
else
return true;
}
return false;
}
};
48 ms 28.7 MB