系列文章目录

算法----滑动窗口
算法----二叉树

---

---

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

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;