文章目錄

• 1.題目
• 2.示例
• 3.答案
• • ①中序遍歷+兩數之和
  • ②遍歷的同時檢查

創(chuàng)新互聯(lián)公司主要從事網頁設計、PC網站建設（電腦版網站建設）、wap網站建設（手機版網站建設）、響應式網站建設、程序開發(fā)、網站優(yōu)化、微網站、重慶小程序開發(fā)公司等，憑借多年來在互聯(lián)網的打拼，我們在互聯(lián)網網站建設行業(yè)積累了豐富的成都網站設計、成都做網站、網站設計、網絡營銷經驗，集策劃、開發(fā)、設計、營銷、管理等多方位專業(yè)化運作于一體。1.題目

給定一個二叉搜索樹 root 和一個目標結果 k，如果二叉搜索樹中存在兩個元素且它們的和等于給定的目標結果，則返回 true。

提示:

• 二叉樹的節(jié)點個數的范圍是 [1, 104].
• -104<= Node.val<= 104
• 題目數據保證，輸入的 root 是一棵 有效 的二叉搜索樹
• -105<= k<= 105

2.示例

輸入: 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);

        //因為不需要節(jié)點的下標，所以可以使用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

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

分享標題：653.兩數之和IV-輸入二叉搜索樹-創(chuàng)新互聯(lián)
文章出自：http://weahome.cn/article/ipisi.html