系列文章目錄

算法----滑動窗口
算法----二叉樹

---

---

二叉搜索樹心法（特性篇）

BST 的特性：

1. 對于 BST 的每一個節點 node，左子樹節點的值都比 node 的值要小，右子樹節點的值都比 node 的值大。

2. 對于 BST 的每一個節點 node，它的左側子樹和右側子樹都是 BST。

從做算法題的角度來看 BST，除了它的定義，還有一個重要的性質：BST 的中序遍歷結果是有序的（升序）。

void traverse(TreeNode* root) {if (root == nullptr)  return;traverse(root->left);// 中序遍歷（升序）print(root->val);traverse(root->right);
}

BST 的中序遍歷代碼可以升序打印節點的值，那如果我想降序打印節點的值怎么辦？很簡單，只要把遞歸順序改一下，先遍歷右子樹，后遍歷左子樹，就能夠降序遍歷節點。

void traverse(TreeNode* root) {if (root == nullptr)  return;traverse(root->right);// 中序遍歷（降序）print(root->val);traverse(root->left);
}

---

二叉搜索樹心法（基操篇）

1、判斷 BST 的合法性

按照 BST 左小右大的特性，每個節點想要判斷自己是否是合法的 BST 節點，要做的事好像是比較自己和左右孩子，比左孩子大，右孩子小。就會寫出這樣的代碼：

bool isValidBST(TreeNode* root) {if (root == nullptr) return true;// root 的左邊應該更小if (root->left != nullptr && root->left->val >= root->val)return false;// root 的右邊應該更大if (root->right != nullptr && root->right->val <= root->val)return false;return isValidBST(root->left)&& isValidBST(root->right);
}

這樣寫出的代碼是錯誤的，BST 的每個節點還要應該要小于右邊子樹的所有節點，下面這個二叉樹顯然不是 BST，因為節點 7 的左子樹中有一個節點 8，但是上面的算法代碼會把它判定為合法 BST：

錯誤的原因在于，對于每一個節點 root，代碼值檢查了它的左右孩子節點是否符合左小右大的原則；但是根據 BST 的定義，root 的整個左子樹都要小于 root.val，整個右子樹都要大于 root.val。

問題是，對于某一個節點 root，他只能管得了自己的左右子節點，怎么把 root 的約束傳遞給左右子樹呢？請看正確的代碼：

class Solution {
public:bool isValidBST(TreeNode* root) {return _isValidBST(root, nullptr, nullptr);}// 定義：該函數返回 root 為根的子樹的所有節點是否滿足 max->val > root->val > min->valbool _isValidBST(TreeNode* root, TreeNode* min, TreeNode* max) {// base caseif (root == nullptr) return true;// 若 root->val 不符合 max 和 min 的限制，說明不是合法 BSTif (min != nullptr && root->val <= min->val) return false;if (max != nullptr && root->val >= max->val) return false;// 根據定義，限定左子樹的最大值是 root->val，右子樹的最小值是 root->valreturn _isValidBST(root->left, min, root) && _isValidBST(root->right, root, max);}
};

2、在 BST 中搜索元素

// 定義：在以 root 為根的 BST 中搜索值為 target 的節點，返回該節點
TreeNode* searchBST(TreeNode* root, int target) {if (root == nullptr) {return nullptr;}// 去左子樹搜索if (root->val > target) {return searchBST(root->left, target);}// 去右子樹搜索if (root->val < target) {return searchBST(root->right, target);}// 當前節點就是目標值return root;
}

3、在 BST 中插入一個數

// 定義：在以 root 為根的 BST 中插入 val 節點，返回插入后的根節點
class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if (root == nullptr) {// 找到空位置插入新節點return new TreeNode(val);}// 去右子樹找插入位置if (root->val < val) {root->right = insertIntoBST(root->right, val);}// 去左子樹找插入位置if (root->val > val) {root->left = insertIntoBST(root->left, val);}// 返回 root，上層遞歸會接收返回值作為子節點return root;}
};

4、在 BST 中刪除一個數

這個問題稍微復雜，跟插入操作類似，先「找」再「改」，先把框架寫出來再說：

TreeNode* deleteNode(TreeNode* root, int key) {if (root->val == key) {// 找到啦，進行刪除} else if (root->val > key) {// 去左子樹找root->left = deleteNode(root->left, key);} else if (root->val < key) {// 去右子樹找root->right = deleteNode(root->right, key);}return root;
}

找到目標節點了，比方說是節點 A，如何刪除這個節點，這是難點。因為刪除節點的同時不能破壞 BST 的性質。有三種情況，用圖片來說明。

• 情況 1：A 恰好是末端節點，兩個子節點都為空，那么它可以直接被刪除。
  

  if (root.left == null && root.right == null)return null;
  

• 情況 2：A 只有一個非空子節點，那么它要讓這個孩子接替自己的位置。
  

  // 排除了情況 1 之后
  if (root.left == null) return root.right;
  if (root.right == null) return root.left;
  

• A 有兩個子節點，麻煩了，為了不破壞 BST 的性質，A 必須找到 左子樹中最大的那個節點，或者右子樹中最小的那個節點 來接替自己。我們以第二種方式講解。
  

  if (root.left != null && root.right != null) {// 找到右子樹的最小節點TreeNode minNode = getMin(root.right);// 把 root 改成 minNoderoot.val = minNode.val;// 轉而去刪除 minNoderoot.right = deleteNode(root.right, minNode.val);
  }
  

三種情況分析完畢，填入框架，最終的代碼：

class Solution {
public:// 定義：在以 root 為根的 BST 中刪除值為 key 的節點，返回完成刪除后的根節點TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return nullptr;if (root->val == key) {// 這兩個 if 把情況 1 和 2 都正確處理了if (root->left == nullptr) return root->right;if (root->right == nullptr) return root->left;// 處理情況 3// 獲得右子樹最小的節點TreeNode* minNode = getMin(root->right);// 刪除右子樹最小的節點root->right = deleteNode(root->right, minNode->val);// 用右子樹最小的節點替換 root 節點minNode->left = root->left;minNode->right = root->right;root = minNode;} else if (root->val > key) {root->left = deleteNode(root->left, key);} else if (root->val < key) {root->right = deleteNode(root->right, key);}return root;}TreeNode* getMin(TreeNode* node) {// BST 最左邊的就是最小的while (node->left != nullptr) node = node->left;return node;}
};

上述代碼在處理情況 3 時通過一系列略微復雜的鏈表操作交換 root 和 minNode 兩個節點：

// 獲得右子樹最小的節點
TreeNode* minNode = getMin(root->right);
// 刪除右子樹最小的節點
root->right = deleteNode(root->right, minNode->val);	//妙筆：用原函數遞歸刪除
// 用右子樹最小的節點替換 root 節點
minNode->left = root->left;
minNode->right = root->right;
root = minNode;