文章目录
1. 题目2. 解题
1. 题目
给出两棵二叉搜索树，请你从两棵树中各找出一个节点，使得这两个节点的值之和等于目标值 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
写一个二叉搜索树的迭代器，一个升序，一个降序双指针一个指向最小的，一个指向最大的，根据情况决定，哪个往下挪
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
);
bst_iter
bstit2(root2
,true);
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
我的博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
