原文：https://labuladong.gitee.io/algo/2/20/41/
二叉搜索树BST并不复杂，但十分重要，许多数据结构（例如：AVL树、红黑树、B+树、线段树等）都是基于BST的思想设计的。BST在二叉树结构基础上有所改变，使其具有“左小右大”的特性：
- 对于 BST 的每一个节点
node，左子树节点的值都比node的值要小，右子树节点的值都比node的值大。 - 对于 BST 的每一个节点
node，它的左侧子树和右侧子树都是 BST。
总而言之，BST左边要比右边大，根节点排在中间。基于BST“左小右大”的特性，衍生出一些做题方向，本篇简要说说二叉搜索树BST刷题总结。
BST中序遍历
BST左子树小于根节点小于右子树，它的中序递归遍历结果是升序的，改变左右子树的递归顺序也可以得到降序结果。
①升序打印节点的值
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.left);
// 中序遍历代码位置
print(root.val);
traverse(root.right);
}
②降序打印结点的值
void traverse(TreeNode root) {
if (root == null) return;
// 先递归遍历右子树
traverse(root.right);
// 中序遍历代码位置
print(root.val);
// 后递归遍历左子树
traverse(root.left);
}
eg：力扣98题判断BST合法性，根据BST中序遍历结果一定是升序，在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可判断BST的合法性。
boolean isValidBST(TreeNode root) {
return inOrder(root);
}
// 记录上一个节点的值，初始值为Long的最小值
long pre = Long.MIN_VALUE;
boolean inorder(TreeNode node) {
if(node == null) return true;
boolean l = inOrder(node.left);
if(node.val <= pre) return false;
//记录上一个节点的值
pre = node.val;
boolean r = inorder(node.right);
return l && r;
}
eg：力扣538题二叉搜索树转化累加树，根据题目要求，我们需要计算大于等于当前值的所有元素之和，调整BST左右子树递归顺序可以得到降序结果，如果设置一个外部累加变量sum，然后将sum赋值给BST每个节点，此题便迎刃而解。
TreeNode convertBST(TreeNode root) {
traverse(root);
return root;
}
// 记录累加和
int sum = 0;
void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.right);
// 维护累加和
sum += root.val;
// 将 BST 转化成累加树
root.val = sum;
traverse(root.left);
}
BST二分搜索
鉴于BST”左小右大“的性质，在BST中做类似二分搜索的操作，每个节点都可以通过对比自身的值判断去左子树还是右子树搜索目标值，减小搜索范围，避免全树遍历，提高搜索效率。
BST常见代码框架：
void BST(TreeNode root, int target) {
if (root.val == target){
// 找到目标，做点什么
}
// 目标大于根节点，右子树搜索
if (root.val < target)
BST(root.right, target);
// 目标小于根节点，左子树搜索
if (root.val > target)
BST(root.left, target);
}
二叉搜索树的基本操作没有写过，又很重要，这次就着BST“二分搜索”一起说了，正好BST的增删查基本操作用到了该思路。对数据结构的操作无非遍历 + 访问，遍历就是「找」，访问就是「改」，「改」在「找」的基础上进行操作，对于二叉树而言，一旦涉及到「改」，函数就要返回TreeNode类型，并对递归调用的返回值进行接收。
在BST中搜索元素
eg：力扣700题二叉搜索树中的搜索，在BST中搜索值为target的节点
TreeNode searchBST(TreeNode root, int target) {
if (root == null) {
return null;
}
// 去左子树搜索
if (root.val > target) {
return searchBST(root.left, target);
}
// 去右子树搜索
if (root.val < target) {
return searchBST(root.right, target);
}
return root;
}
在BST中插入一个数
eg：力扣701题 二叉搜索树的插入操作，插入一个数，就是先找到插入位置，然后进行插入操作。
TreeNode insertIntoBST(TreeNode root, int val) {
// 找到空位置插入新节点
if (root == null) return new TreeNode(val);
// if (root.val == val)
// BST 中一般不会插入已存在元素
if (root.val < val)
root.right = insertIntoBST(root.right, val);
if (root.val > val)
root.left = insertIntoBST(root.left, val);
return root;
}
由于BST根节点子树数量固定（2）且左小右大，插入的数最后一定是叶子节点，不会对整个树造成破坏。
在BST中删除一个数
eg：力扣450题 删除二叉搜索树中的节点，删除的节点可能是叶子节点，可能有一个孩子节点，可能有两个孩子节点。叶子节点可以直接删，有孩子节点删除的话会破坏整个二叉树的结构，导致二叉树不满足左小右大的性质，需要重构BST。
- 删除节点正好是末端节点，直接删除
if (root.left == null && root.right == null)
return null;
删除节点有一个孩子，由于BST左侧所有的节点都小于右侧所有的节点，同侧树枝性质相同，删除节点，可以直接让该节点的孩子接替自己（各种情况可以一一列举）。
// 排除了情况 1 之后
if (root.left == null) return root.right;
if (root.right == null) return root.left;
3.删除节点有两个节点，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己，而BST中最左边的就是最小的，最右边就是最大的。我们以第二种方式讲解。
if (root.left != null && root.right != null) {
// 找到右子树的最小节点
TreeNode minNode = getMin(root.right);
// 把 root 改成 minNode
root.val = minNode.val;
// 转而去删除 minNode
root.right = deleteNode(root.right, minNode.val);
}
删除BST中节点解法：
TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (root.val == key) {
// 这两个 if 把情况 1 和 2 都正确处理了
if (root.left == null) return root.right;
if (root.right == null) 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 != null) node = node.left;
return node;
}
注意：
删除BST节点中，对于情况3的处理是交换节点而不是改节点中的字段，因为我们希望将BST当作工具，它的操作应该与其中存储的数据无关，所以我们更倾向于使用指针操作来交换节点，不关心内部数据，不对内部数据造成影响。而且在实际应用中，BST 节点内部的数据域通常是用户自定义的，可以非常复杂，交换数据非常麻烦。
BST的优化
待更。。。
