建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
653.兩數(shù)之和IV-輸入二叉搜索樹-創(chuàng)新互聯(lián)
文章目錄
文章名稱：653.兩數(shù)之和IV-輸入二叉搜索樹-創(chuàng)新互聯(lián)
標題URL：http://fisionsoft.com.cn/article/ipisi.html
- 1.題目
- 2.示例
- 3.答案
- ①中序遍歷+兩數(shù)之和
- ②遍歷的同時檢查
給定一個二叉搜索樹 root 和一個目標結果 k，如果二叉搜索樹中存在兩個元素且它們的和等于給定的目標結果，則返回 true。
提示:
- 二叉樹的節(jié)點個數(shù)的范圍是 [1, 104].
- -104<= Node.val<= 104
- 題目數(shù)據(jù)保證，輸入的 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將問題拆成兩步，第一部得到二叉樹的遍歷序列，第二步檢查是否存在兩數(shù)之和為k. (兩數(shù)之和)。
既然要得到遍歷序列，對于一棵有效的二叉搜索樹中序遍歷的結果是一個沒有重復元素的有序序列。
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);
//因為不需要節(jié)點的下標，所以可以使用set存儲而不是map記錄下標和值的映射關系
//只需要判斷元素是否存在。
unordered_sets;
for(int i:res){// find返回迭代器,count返回個數(shù)
if(s.count(k-i)) return true; //可以再元素i前找到k-i
s.insert(i); //將i插入
}
return false;
} 將中序遍歷與兩數(shù)之和的檢查結合起來。
對應元素之和是否為k，如果想要一次遍歷就查找成功，就要避免相同元素的重復利用。先在之前經(jīng)過的元素里查找是否可以和當前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
你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
文章名稱：653.兩數(shù)之和IV-輸入二叉搜索樹-創(chuàng)新互聯(lián)
標題URL：http://fisionsoft.com.cn/article/ipisi.html
