Leetcode刷題學習筆記 – Binary Search Tree(BST)

簡介

ref : wiki
二元搜尋樹（英語：Binary Search Tree），也稱為有序二元樹（ordered binary tree）或排序二元樹（sorted binary tree），是指一棵空樹或者具有下列性質的二元樹：

  1. 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
  2. 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；
  3. 任意節點的左、右子樹也分別為二元搜尋樹；

BST

如果BST，呈現不平衡的狀態，例如都串在同一個直線。那最差情況都是O(n)。

演算法 平均 最差
空間 O(n) O(n)
搜尋 O(logn) O(n)
插入 O(logn) O(n)
刪除 O(logn) O(n)

二元搜尋樹的最壞效率是O(n)，但它支援動態查詢，且有很多改進版的二元搜尋樹可以使樹高為O(log n)，從而將最壞效率降至O(log n)，如AVL樹、紅黑樹等。

Inorder Traversal

當BST(Binary Search Tree)使用Inorder Traversal的時候，可以得到遞增或是遞減的數列。

以下的程式碼是得到遞增序列。

void dfs(TreeNode *root, vector<int>& rtn) {
    if(!root) return;
    dfs(root->left);
    rtn.push_back(root->val);
    dfs(root->right);
}

以下的程式碼可以得到遞減序列。

void dfs(TreeNode *root, vector<int>& rtn) {
    if(!root) return;
    dfs(root->right);
    rtn.push_back(root->val);
    dfs(root->left);
}

另外也可以用stack來實現

void inorder(TreeNode *root) {
    stack<TreeNode *> st;
    TreeNode *p = root;
    while(p || !st.empty()) {
        // 先把全部的left存起來
        while(p) {
            st.push(p);
            p = p->left;
        }
        // 取出最後一個left node
        p = st.top(); st.pop();
        cout << p->val << endl;
        // 檢查right child node
        p = p->right;
    }
}

很多題目會根據上訴兩種來變形。

  1. 遞增訪問
  2. 遞減訪問
  3. 找兩個node之間最小的差

99. Recover Binary Search Tree

在BST中有兩個node被交換了，試復原成原本的BST。

  1. 使用inorder traversal。如果是正常的BST會得到從小到大的排列。
  2. 題目只有兩個node被交換了，例如
    1, 2, 3, 4, 5, 6 –> 1, 5, 3, 4, 2, 6
    5, 3 –> prev > curr, 取前者
    4, 2 –> prev > cur, 取後者
void recoverTree(TreeNode* root) {
    TreeNode *prev = nullptr, *first = nullptr, *second = nullptr, *p = root;
    stack<TreeNode *> st;
    while(p || !st.empty()) {
        while(p) {
            st.push(p);
            p = p->left;
        }
        p = st.top(); st.pop();
        if(prev && prev->val > p->val) {
            if(!first) first = prev; // 取前者
            second = p; // 取後者
        }
        prev = p;
        p = p->right;
    }
    swap(first->val, second->val);
}

230. Kth Smallest Element in a BST

找出BST中，第k個最小的值。

  1. 在BST中使用Inorder Traversal來找出第k個數值。
class Solution {
    int k, rtn;
    void helper(TreeNode *root) {
        if(!root) return;
        helper(root->left);
        k--;
        if(k == 0) rtn = root->val;
        else if(k < 0) return;
        helper(root->right);
    }
public:
    int kthSmallest(TreeNode* root, int k) {
        this->k = k;
        helper(root);
        return rtn;
    }
};

897. Increasing Order Search Tree

把BST，從小到大，依序串在node的右邊。
897Example

  1. 對BST做Inorder Traversal。
  2. 對每個node，把left child設成nullptr, 把right child設成下一個走訪的node。
class Solution {
    void helper(TreeNode *root) {
        if(!root) return;
        helper(root->left);
        root->left = nullptr;
        cur->right = root;
        cur = cur->right;
        helper(root->right);
    }
    TreeNode *cur;
public:
    TreeNode* increasingBST(TreeNode* root) {
        TreeNode *newroot = new TreeNode();
        cur = newroot;
        helper(root);
        return newroot->right;
    }
};

538. Convert BST to Greater Tree

給你一個BST，試給出一個Greater Tree。
538_Example

  1. 對BST做Inorder Traversal(從大到小)。
  2. 每遇到一個node就把數值相加，並更新到目前的node。
class Solution {
    int sum = 0;
    void helper(TreeNode *root) {
        if(!root) return;
        helper(root->right);
        sum += root->val;
        root->val = sum;
        helper(root->left);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        helper(root);
        return root;
    }
};

450. Delete Node in a BST(Medium)

給你一個key，刪除BST中和key值一樣的node，並且保持原本的樹還是BST。

例如:
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]

450 Example

解題思路:

case 1: 如果要刪除的node是leaf，那就直接刪除。
case 2: 如果要刪除的node不是leaf，但是只有一個child，則直接把child接上來。
case 3: 如果要刪除的node不是leaf，而且有兩個child!，為了保持刪除後依然是BST，所以勢必要調整樹的結構。如何做到最小調整? 使用右子樹最小值，或是左子樹最大值代替原本欲刪除的node，就可以達到最小的修正。























TreeNode* deleteNode(TreeNode* root, int key) {
    if(!root) return nullptr;
    if(key > root->val)
        root->right = deleteNode(root->right, key);
    else if(key < root->val)
        root->left = deleteNode(root->left, key);
    else {
        // 只有一個child node，或是node為leaf
        if(!root->left || !root->right)
            root = root->left ? root->left : root->right;
        else {
            // node有兩個child
            // 找出右子樹最小值
            TreeNode *cur = root->right;
            while(cur->left) cur = cur->left;
            root->val = cur->val;
            // 刪除右子樹最小值的node
            root->right = deleteNode(root->right, cur->val);
        }
    }
    return root;
}

找出左邊子樹的最大值一樣也可以。







// 找出左子樹最大值
TreeNode *cur = root->left;
while(cur->right) cur = cur->right;
root->val = cur->val;
// 刪除左子樹最大值的node
root->left = deleteNode(root->left, cur->val);

235. Lowest Common Ancestor of a Binary Search Tree(Easy)

給你兩個在BST中的node, p和q。找出這兩個的共同祖先(ancestor)。

  1. 因為沒說明p, q是否有什麼關係，所以必須用max(), min()找出最大最小值。
  2. root->val > max(p->val, q->val) 表示p和q都在root的左側。
  3. root->val < min(p->val, q->val) 表示p和q都在root的右側。
  4. 不是上述兩種狀況表示root即為共同的祖先。









TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(!root) return nullptr;
    else if(root->val > max(p->val, q->val))
        return lowestCommonAncestor(root->left, p, q);
    else if(root->val < min(p->val, q->val))
        return lowestCommonAncestor(root->right, p, q);
    else // root->val > min(p->val, q->val) && root->val < max(p->val, q->val)
        return root;       
}

783. Minimum Distance Between BST Nodes

在BST中，找出兩個node之間最小的差。

  1. 因為BST使用inorder traversal可以得到遞增數列，使用此特性比較前後兩個node，就可以找出最小的差值。


















class Solution {
    // 在BST中使用inorder可以得到從小到大的排序。
    int ans = 1e5 + 1, prev = -1;
    void helper(TreeNode *root) {
        if(!root) return;
        helper(root->left);
        if(prev != -1)
            ans = min(ans, root->val - prev);
            
        prev = root->val;
        helper(root->right);
    }
public:
    int minDiffInBST(TreeNode* root) {
        helper(root);
        return ans;
    }
};
tags: leetcode 刷題
Select a repo