• 📚 博客主頁：??這是一只小逸白的博客鴨~??
• 👉 歡迎 關注??點贊👍收藏??評論📝
• 😜 小逸白正在備戰實習，經常更新面試題和LeetCode題解，歡迎志同道合的朋友互相交流~
• 💙 若有問題請指正，記得關注哦，感謝~

往期文章 ：

• LeetCode 劍指 Offer II 鏈表 專題總結
• LeetCode 劍指 Offer II 哈希表 專題總結
• LeetCode 劍指 Offer II 堆疊 專題總結
• LeetCode 劍指 Offer II 佇列 專題總結
• LeetCode 劍指 Offer II 樹（上） 專題總結

先補充一個函式知識點，最后兩題會用到：

set、map：

• lower_bound()：二分查找一個有序集合，回傳第一個>= num的數，如果沒找到，回傳末尾的迭代器位置
• upper_bound()：二分查找一個有序集合，回傳第一個> num的數，如果沒找到，回傳末尾的迭代器位置

vector：
在從小到大的排序陣列中

• lower_bound( begin,end,num)：從陣列的begin位置到end-1位置二分查找第一個 >= num 的數字
• upper_bound( begin,end,num)：從陣列的begin位置到end-1位置二分查找第一個 > num 的數字
  在從大到小的排序陣列中
• lower_bound( begin,end,num)：從陣列的begin位置到end-1位置二分查找第一個 <= num 的數字
• upper_bound( begin,end,num)：從陣列的begin位置到end-1位置二分查找第一個 < num 的數字

053. 二叉搜索樹中的中序后繼

題目：

給定一棵二叉搜索樹和其中的一個節點 p ，找到該節點在樹中的中序后繼，如果節點沒有中序后繼，請回傳 null ，
節點 p 的后繼是值比 p.val 大的節點中鍵值最小的節點，即按中序遍歷的順序節點 p 的下一個節點，

示例：

輸入：root = [5,3,6,2,4,null,null,1], p = 6
輸出：null
解釋：因為給出的節點沒有中序后繼，所以答案就回傳 null 了，

提示：

• 樹中節點的數目在范圍 [1, 104] 內，
• -105 <= Node.val <= 105
• 樹中各節點的值均保證唯一，

思路：

用一個res記錄大于 p 的節點，每次深搜都會逐漸靠近

• 當前節點大于目標節點就往左邊查找，保存當前節點（當前節點大于目標節點）
• 否則往右邊查找

class Solution {
public:
    TreeNode* res = NULL;
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        dfs(root, p);
        return res;
    }
    void dfs(TreeNode* root, TreeNode* p) {
        if(root == NULL) return ;
        if(root->val > p->val) {
            res = root;
            dfs(root->left, p);
        }else 
            dfs(root->right, p);
    }
};

054. 所有大于等于節點的值之和

題目：

給定一個二叉搜索樹，請將它的每個節點的值替換成樹中大于或者等于該節點值的所有節點值之和，
提醒一下，二叉搜索樹滿足下列約束條件：

• 節點的左子樹僅包含鍵 小于 節點鍵的節點，
• 節點的右子樹僅包含鍵 大于 節點鍵的節點，
• 左右子樹也必須是二叉搜索樹，

示例：

輸入：root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
輸出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

提示：

• 樹中的節點數介于 0 和 104 之間，
• 每個節點的值介于 -104 和 104 之間，
• 樹中的所有值 互不相同 ，
• 給定的樹為二叉搜索樹，

思路：

遍歷順序：右 - 中 - 左 ， ans記錄當前遍歷過的節點和，記得更新root->val

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int ans = 0;
        dfs(root, ans);
        return root;
    }
    //右 - 中 - 左 遍歷， ans記錄和
    void dfs(TreeNode* root, int& ans) {
        if(root == nullptr) return ;
        dfs(root->right, ans);

        root->val += ans;
        ans = root->val;
        
        dfs(root->left, ans);

    }
};

055. 二叉搜索樹迭代器

題目：

實作一個二叉搜索樹迭代器類BSTIterator ，表示一個按中序遍歷二叉搜索樹（BST）的迭代器：

• BSTIterator(TreeNode root) 初始化 BSTIterator 類的一個物件，BST 的根節點 root 會作為建構式的一部分給出，指標應初始化為一個不存在于 BST 中的數字，且該數字小于 BST 中的任何元素，
• boolean hasNext() 如果向指標右側遍歷存在數字，則回傳 true ；否則回傳 false ，
• int next()將指標向右移動，然后回傳指標處的數字，
  注意，指標初始化為一個不存在于 BST 中的數字，所以對 next() 的首次呼叫將回傳 BST 中的最小元素，

可以假設 next() 呼叫總是有效的，也就是說，當呼叫 next() 時，BST 的中序遍歷中至少存在一個下一個數字，

示例：

輸入
inputs = [“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”]
inputs = [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
輸出
[null, 3, 7, true, 9, true, 15, true, 20, false]
解釋
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 回傳 3
bSTIterator.next(); // 回傳 7
bSTIterator.hasNext(); // 回傳 True
bSTIterator.next(); // 回傳 9
bSTIterator.hasNext(); // 回傳 True
bSTIterator.next(); // 回傳 15
bSTIterator.hasNext(); // 回傳 True
bSTIterator.next(); // 回傳 20
bSTIterator.hasNext(); // 回傳 False

提示：

• 樹中節點的數目在范圍 [1, 105] 內
• 0 <= Node.val <= 106
• 最多呼叫 105 次 hasNext 和 next 操作

思路：

將二叉搜索樹中序遍歷并存盤到陣列中，通過陣列實作next()， hasNext() 就簡單多了

class BSTIterator {
private:
    vector<int> arr;
    int index = 0;
    //中序遍歷并存盤到陣列中
    void dfs(TreeNode* root) {
        if(!root) return ;
        dfs(root->left);
        arr.push_back(root->val);
        dfs(root->right);
    }

public:
    
    BSTIterator(TreeNode* root) {
        dfs(root);
    }
    
    int next() {
        return arr[index++];
    }
    
    bool hasNext() {
        if(index < arr.size())
            return true;
        else
            return false;
    }
};

056. 二叉搜索樹中兩個節點之和

題目：

給定一個二叉搜索樹的 根節點 root 和一個整數 k , 請判斷該二叉搜索樹中是否存在兩個節點它們的值之和等于 k ，假設二叉搜索樹中節點的值均唯一，

示例：

輸入: root = [8,6,10,5,7,9,11], k = 12
輸出: true
解釋: 節點 5 和節點 7 之和等于 12

提示：

• 二叉樹的節點個數的范圍是 [1, 104].
• -104 <= Node.val <= 104
• root 為二叉搜索樹
• -105 <= k <= 105

思路：

將遍歷過的值存盤在 map 中，通過map[k - root->val]去map中尋找答案

class Solution {
public:
    bool ok = false;
    unordered_map<int, int> map;
    bool findTarget(TreeNode* root, int k) {
        dfs(root, k);
        return ok;
    }
    void dfs(TreeNode* root, int k) {
        if(root == nullptr || ok) return ;
        if(map[k - root->val]) {
            ok = true;
            return ;
        }
        map[root->val]++;
        dfs(root->left, k);
        dfs(root->right, k);
    }
};

057. 值和下標之差都在給定的范圍內

題目：

給你一個整數陣列 nums 和兩個整數 k 和 t ，請你判斷是否存在 兩個不同下標 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同時又滿足 abs(i - j) <= k ，
如果存在則回傳 true，不存在回傳 false，

示例：

輸入：nums = [1,2,3,1], k = 3, t = 0
輸出：true

提示：

• 0 <= nums.length <= 2 * 104
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 104
• 0 <= t <= 231 - 1

思路：

用滑動窗視窗來約束一定在 k 內
abs(a - b) <= t 情況下， b肯定在[a-t, b+t] (t>0) 區間內
所以求出上限，下限，然后通過 lower_bound() 求出大于等于下限的數，再判斷是否小于等于上限即可

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long> set;
        for (int i = 0; i < nums.size(); ++i) {
            //下限
            long lowerLimit = (long)nums[i] - t;
            //上限
            long upperLimit = (long)nums[i] + t;
            //查找大于等于下限的數
            auto it = set.lower_bound(lowerLimit);
            if (it != set.end() && *it <= upperLimit) {
                return true;
            }
            set.insert(nums[i]);
            //滑動視窗
            if (i >= k) {
                set.erase(nums[i - k]);
            }
        }
        return false;
    }
};

058. 日程表

題目：

請實作一個 MyCalendar 類來存放你的日程安排，如果要添加的時間內沒有其他安排，則可以存盤這個新的日程安排，
MyCalendar 有一個 book(int start, int end)方法，它意味著在 start 到 end 時間內增加一個日程安排，注意，這里的時間是半開區間，即 [start, end), 實數 x 的范圍為， start <= x < end，
當兩個日程安排有一些時間上的交叉時（例如兩個日程安排都在同一時間內），就會產生重復預訂，
每次呼叫 MyCalendar.book方法時，如果可以將日程安排成功添加到日歷中而不會導致重復預訂，回傳 true，否則，回傳 false 并且不要將該日程安排添加到日歷中，
請按照以下步驟呼叫 MyCalendar 類: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

示例：

輸入:
[“MyCalendar”,“book”,“book”,“book”]
[[],[10,20],[15,25],[20,30]]
輸出: [null,true,false,true]
解釋:
MyCalendar myCalendar = new MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false ，第二個日程安排不能添加到日歷中，因為時間 15 已經被第一個日程安排預定了
MyCalendar.book(20, 30); // returns true ，第三個日程安排可以添加到日歷中，因為第一個日程安排并不包含時間 20

提示：

• 每個測驗用例，呼叫 MyCalendar.book 函式最多不超過 1000次，
• 0 <= start < end <= 109

思路：

題目一堆廢話，就是要判斷區間是否交叉
要判斷當前區間是否能夠存入 map ，滿足一下兩個條件就可以

• 用lower_bound() 求出大于等于start的數，這個數的start 要大于 插入數 的end
• lower_bound()數的前一個數，這個數的 end 要小于插入數的 start

class MyCalendar {
public:
    map<int, int> map;
    MyCalendar() {

    }
    
    bool book(int start, int end) {
        // 查找第一個大于等于start的元素
        auto iter = map.lower_bound(start);
        // (iter)第一個大于等于插入元素的時間段，這個時間段的起始時間不能小于插入時間的終止時間
        if(iter != map.end() && iter->first < end) 
            return false;
        // (--iter)最后一個小于等于插入元素的時間段，這個時間段的終止時間不能大于插入的起始時間
        if(iter != map.begin() && (--iter)->second > start)
            return false;
        // 保存時間段
        map[start] = end;
        return true;
    }
};