LeetCode 653. 【递归】BST两数之和
原题链接
简单
作者:
大明湖的鱼
,
2021-01-24 11:33:30
,
所有人可见
,
阅读 385
思路
- 前序遍历,先找set中有没有适合当前节的。
- 如果没有,则把当前节点加入set
- 遍历左子树和右子树,或 连接,因为只要满足一对就可以
- 节点是逐个加入的,2+6 = 8 的情况是,如果2先加入,可能匹配不上,但是等之后4加入以后,就能匹配上了
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
set<int> st;
return find(root,k,st);
}
bool find(TreeNode* root ,int k,set<int>& st){
if(root == nullptr) return false;
if(st.find(k-root->val)!=st.end())return true;
st.insert(root->val);
return find(root->left,k,st) || find(root->right,k,st);
}
};