653.两数之和IV-输入二叉搜索树-创新互联
文章目录
文章名称:653.两数之和IV-输入二叉搜索树-创新互联
文章转载:http://myzitong.com/article/ipisi.html
- 1.题目
- 2.示例
- 3.答案
- ①中序遍历+两数之和
- ②遍历的同时检查
给定一个二叉搜索树 root 和一个目标结果 k,如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果,则返回 true。
提示:
- 二叉树的节点个数的范围是 [1, 104].
- -104<= Node.val<= 104
- 题目数据保证,输入的 root 是一棵 有效 的二叉搜索树
- -105<= k<= 105
输入: root = [5,3,6,2,4,null,7], k = 9
输出: true
输入: root = [5,3,6,2,4,null,7], k = 28
输出: false
3.答案
①中序遍历+两数之和将问题拆成两步,第一部得到二叉树的遍历序列,第二步检查是否存在两数之和为k. (两数之和)。
既然要得到遍历序列,对于一棵有效的二叉搜索树中序遍历的结果是一个没有重复元素的有序序列。
void inorder(TreeNode*root,vector&res){//中序遍历
if(!root) return ;
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
bool findTarget(TreeNode* root, int k) {vectorres;
inorder(root,res);
//因为不需要节点的下标,所以可以使用set存储而不是map记录下标和值的映射关系
//只需要判断元素是否存在。
unordered_sets;
for(int i:res){// find返回迭代器,count返回个数
if(s.count(k-i)) return true; //可以再元素i前找到k-i
s.insert(i); //将i插入
}
return false;
}
②遍历的同时检查将中序遍历与两数之和的检查结合起来。
对应元素之和是否为k,如果想要一次遍历就查找成功,就要避免相同元素的重复利用。先在之前经过的元素里查找是否可以和当前root->val构成k,找不到的话在插入root->val。此时不会利用同一个超过一次。
// 改变中序遍历的操作来检查
bool infind(TreeNode* root,int k,unordered_set&s){if(!root) return false;
if(s.count(k-root->val)) return true;
s.insert(root->val);
return infind(root->left,k,s)||infind(root->right,k,s);
}
bool findTarget(TreeNode* root, int k) {unordered_sets;
return infind(root,k,s);
}
// 利用BFS(或者树的层次遍历的同时检查)
//遍历的顺序并不重要,重点是在先前序列里检查,在插入自身,避免元素重复利用
bool findTarget(TreeNode* root, int k) {unordered_sets;
queueq;
q.push(root);
while(!q.empty()){TreeNode*tmp=q.front();
q.pop();
if(s.count(k-tmp->val)) return true;
s.insert(tmp->val);
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
return false;
}
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/two-sum-iv-input-is-a-bst
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
文章名称:653.两数之和IV-输入二叉搜索树-创新互联
文章转载:http://myzitong.com/article/ipisi.html