leetcode算法之二叉搜索樹

• 2021 年 2 月 6 日
• AI
• C/C++/C#

今天來盤一盤 **二叉搜索樹 ** 這類題目

使用python刷題分類整理的筆記,請參考: //github.com/lxztju/leetcode-algorithm/tree/v1

二叉搜索樹

二叉搜索樹是指 左子樹的節點值均小於根節點的值， 右子樹的節點值大於根節點的值（遞歸的概念，對於每個節點都成立）

二叉搜索樹的中序遍歷是排序數組

• 235 二叉搜索樹的最近公共祖先 (Easy)
• 108 將有序數組轉換為二叉搜索樹 (Easy)
• 653 兩數之和 IV – 輸入 BST (Easy)
• 530 二叉搜索樹的最小絕對差 (Easy)
• 501 二叉搜索樹中的眾數 (Easy)
• 669 修剪二叉搜索樹 (medium)
• 230 二叉搜索樹中第K小的元素 (Medium)
• 538 把二叉搜索樹轉換為累加樹 (medium)
• 109 有序鏈錶轉換二叉搜索樹 (Medium)
• 236 二叉樹的最近公共祖先 (Medium)

235 二叉搜索樹的最近公共祖先 (Easy)

• 如果當前節點值大於pq，那麼說明分叉點存在於當前節點的左子樹中
• 如果當前節點值小於pq， 那麼說明分叉點存在當前節點的右子樹中
• 否則，說明找到分叉點。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return nullptr;
        // 大於pq，搜索左子樹
        if(root->val > p->val && root->val > q->val) 
            return lowestCommonAncestor(root->left, p, q);
        // 小於pq，搜索右子樹
        else if (root->val < p->val && root->val < q->val)
            return lowestCommonAncestor(root->right, p, q);
       	// 找到分叉點。
        else    
            return root;
    }
};

108 將有序數組轉換為二叉搜索樹 (Easy)

• 二叉搜索樹的中序遍歷是有序數組
• 根據這個性質，排序數組的中間元素是根節點，左半部分是左子樹，右半部分是右子樹，遞歸構建

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArray2BST(nums, 0, nums.size()-1);
    }
    TreeNode* sortedArray2BST(vector<int>& nums, int left, int right){
        if (left > right) return nullptr;
        int middle = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[middle]);
        root->left = sortedArray2BST(nums, left, middle-1);
        root->right = sortedArray2BST(nums, middle+1, right);
        return root;
    }
};

653 兩數之和 IV – 輸入 BST (Easy)

• 中序遍歷得到排序數組
• 然後雙指針

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        vector<int> nums;
        inorder(root, nums);
        int l = 0, r = nums.size() -1;
        while (l < r){
            int lrSum = nums[l] + nums[r];
            if (lrSum == k)
                return true;
            else if (lrSum > k)
                r--;
            else 
                l++;
        }
        return false;
    }
	//中序遍歷
    void inorder(TreeNode* root, vector<int>& nums){
        if (root == nullptr) return;
        inorder(root->left, nums);
        nums.push_back(root->val);
        inorder(root->right, nums);
    }
};

530 二叉搜索樹的最小絕對差 (Easy)

• 依然利用中序遍歷為有序數組的特點。

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        vector<int> nums;
        inorder(root, nums);
        int res = nums[1] - nums[0];
        for (int i = 1; i < nums.size(); i++){
            res = min(res, nums[i] - nums[i-1]);
        }
        return res;
    }
	//中序遍歷
    void inorder(TreeNode* root, vector<int>& nums){
        if (root == nullptr) return;
        inorder(root->left, nums);
        nums.push_back(root->val);
        inorder(root->right, nums);
    }
};

501 二叉搜索樹中的眾數 (Easy)

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        // 直接使用unordered_map，沒有用到二叉搜索樹的特定
        unordered_map<int, int> nodeFreq;
        vector<int> res;
        traversal(root, nodeFreq);
        int freq = 0;
        for (auto e = nodeFreq.begin(); e != nodeFreq.end(); e++){
            freq = max(freq, e->second);
        }
        for (auto e = nodeFreq.begin(); e != nodeFreq.end(); e++){
            if (e->second == freq)
                res.push_back(e->first);
        }
        return res;
    }
    void traversal(TreeNode* root, unordered_map<int, int>& nodeFreq){
        if (root == nullptr) return;
        nodeFreq[root->val]++;
        traversal(root->left, nodeFreq);
        traversal(root->right, nodeFreq);
    }
};

如果不使用額外的空間。

• 針對二叉搜索樹而言，其中序遍歷是一個有序數組， 所有相等的元素均在一起出現
• 利用cnt變量來統計當前元素出現的次數， maxcnt為最大頻率的元素出現的次數，res保存眾數

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        int cnt = 1;
        int maxcnt = 1;
        int base;
        inorder(root, cnt, maxcnt, res, base);
        return res;
    }
    void inorder(TreeNode* root, int& cnt, int& maxcnt, vector<int>& res, int& base){
        if (root == nullptr) return;
        
        inorder(root->left, cnt, maxcnt, res, base);

        if (root->val == base){
            cnt++;
        }
        else{
            cnt = 1;
            base = root->val;
        }
        if (cnt > maxcnt){
            res.clear();
            res.push_back(base);
            maxcnt = cnt;
        }
        else if (cnt == maxcnt){
            res.push_back(base);
        }

        inorder(root->right, cnt, maxcnt, res, base);
    }
};

669 修剪二叉搜索樹 (medium)

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root == nullptr) return nullptr;
        if (root->val < low)
            return trimBST(root->right, low, high);
        else if (root->val > high)
            return trimBST(root->left, low, high);
        else{
            root->left = trimBST(root->left, low, high);
            root->right = trimBST(root->right, low, high);
        }
        return root;
    }
};

230 二叉搜索樹中第K小的元素 (Medium)

• 最直觀的想法，二叉搜索樹的中序遍歷為排序數組

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<int> nums;
        inorder(root, nums);
        return nums[k-1];
    }

    //中序遍歷
    void inorder(TreeNode* root, vector<int>& nums){
        if (root == nullptr) return;
        inorder(root->left, nums);
        nums.push_back(root->val);
        inorder(root->right, nums);
    }
};

538 把二叉搜索樹轉換為累加樹 (medium)

• 反中序遍歷
• 從最右側看，根節點的值為根+=右子樹的值
• 左子樹的值為左子樹的值+=根的值

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int val = 0;
        inverseInorder(root, val);
        return root;
    }
    // 反中序遍歷
    void inverseInorder(TreeNode* root, int& val){
        if (root == nullptr) return;
        inverseInorder(root->right, val);
        val += root->val;
        root->val  = val;
        inverseInorder(root->left, val);
    }
};

109 有序鏈錶轉換二叉搜索樹 (Medium)

• 有序鏈錶轉換為二叉搜索樹與數組的轉換方式基本一致
• 只需要將鏈表分為左右兩部分分別構成BST的左右子樹即可

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (head == nullptr) return nullptr;
        // 返回鏈表中間節點的前驅節點
        ListNode* premiddle = premiddleList(head);
        cout<< (premiddle->val) << endl;
        // 鏈表的中間節點
        int val = 0;
        ListNode* middle = premiddle->next;
        if (middle == nullptr) {
            TreeNode* root = new TreeNode(premiddle->val);
            return root;
        }
        else{
            TreeNode* root = new TreeNode(middle->val);
            premiddle->next = nullptr;
            root->left = sortedListToBST(head);
            root->right = sortedListToBST(middle->next);
            return root;
        }
    }


    // 獲得鏈表的中間節點的前一個節點。
    ListNode* premiddleList(ListNode* head){
        if ( head == nullptr) return nullptr;
        ListNode* slow = head;
        ListNode* pre = slow;
        ListNode* fast = head->next;
        while (fast != nullptr && fast->next != nullptr){
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        return pre;
    }
};

236 二叉樹的最近公共祖先 (Medium)

• 直接遍歷查找，如果一棵樹的左右子樹中分別存在p與q，那麼直接返回這個結點

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return nullptr;
        if ( root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != nullptr && right != nullptr) return root;
        else if (left == nullptr)
            return right;
        else if (right == nullptr)
            return left; 
        else return nullptr;
    }
};

更多分類刷題資料

• 微信公眾號： 小哲AI

  

• GitHub地址： //github.com/lxztju/leetcode-algorithm

• csdn博客： //blog.csdn.net/lxztju

• 知乎專欄： 小哲AI

• AI研習社專欄：小哲AI