(刷題筆記)Leetcode 653.兩數之和 IV - 輸入 BST

目錄

• 題目
• 解題思路
• 代碼(C++)

題目

給定一個二叉搜尋樹和一個目标結果，如果 BST 中存在兩個元素且它們的和等于給定的目标結果，則傳回 true。

案例 1:

輸入:

5
   / \
  3   6
 / \   \
2   4   7
           

Target = 9

輸出: True

案例 2:

輸入:

5
   / \
  3   6
 / \   \
2   4   7
           

Target = 28

輸出: False

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst

解題思路

這是一道稍微綜合性的題目，考察了二叉樹搜尋樹的性質和二分查找算法。

首先是對二叉搜尋樹進行中序周遊，用一個vector記錄中序周遊結果。

因為二叉搜尋樹的中序周遊結果是有序的，是以對于K的搜尋可以用二分查找法

維護一個left和right的指針（廣義的，實際指數組下标），left指向vector的頭，right指向vector的尾

比較vec[left]+vec[right]與K的大小，大于K說明vec[right]大了，right–；小于K說明vec[left]小了，left++；

等于直接傳回true；跳出條件是left>right的時候，說明沒有找到。

話說我一開始寫的時候沒有想到二分，用雙重循環暴力搜尋，送出的用時和二分竟然是一樣的，不知道是不是測試資料的問題。

代碼(C++)

疊代

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool findTarget(TreeNode* root, int k) {

        stack<TreeNode*> st;
        vector<int> vec;
        TreeNode* temp=root;

        while(!st.empty()||temp){

            while(temp){
                st.push(temp);
                temp=temp->left;
            }
            temp=st.top();
            st.pop();
            vec.push_back(temp->val);
            temp=temp->right;
        }

        int left=0;
        int right=vec.size()-1;
        while(left<right){

            if(vec[left]+vec[right]<k) left++;
            else if(vec[left]+vec[right]>k) right--;
            else return true;  
        }

        return false;

    }
};
           

遞歸

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* root,vector<int> &vec){
        if(root==NULL) return;
        dfs(root->left,vec);
        vec.push_back(root->val);
        dfs(root->right,vec);
    }

    bool findTarget(TreeNode* root, int k) {

        vector<int> vec;
        dfs(root,vec);

        int left=0;
        int right=vec.size()-1;

        while(left<right){
            if(k>vec[left]+vec[right]) left++;
            else if(k<vec[left]+vec[right]) right--;
            else return true;
        }
       
        return false;
    
    }
};