1.二叉搜索树的特性：
1 对于二叉搜索树的每一个节点，其左子树节点的值都不大于该节点的值，右子树节点的值都不小于该节点的值；
2 对于二叉搜索树的每一个节点，其左子树和右子树均为二叉搜索树；
2.二叉搜索树的一条重要性质：
对BST中序遍历的结果是一个有序、且为升序的结果。这个结论可以用在很多题目上。
例1 LeetCode 230题：BST中第k小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
分析：利用2所提及的BST的性质即可。因为BST中序遍历的结果是升序排列的，在中序遍历BST的过程中，即可找到第k小的元素。
class Solution {
private int count = 0;
private int num = Integer.MIN_VALUE;
public int kthSmallest(TreeNode root, int k) {
hlp(root, k);
return num;
}
private void hlp(TreeNode node, int k){
if(node == null) return;
hlp(node.left, k);
count++;
if(count == k){
num = node.val;
return;
}
hlp(node.right, k);
}
}
3.二叉搜索树之判断合法性 LeetCode 98题：验证BST
判断BST的合法性即判断某个二叉树是否是BST，满足BST的定义。
看下面这段代码：
boolean isValidBST(TreeNode node){
if(node == null) return true;
if(node.left != null && node.val < node.left.val) return false;
if(node.right!= null && node.val > node.right.val) return false;
return isValidBST(node.left) && isValidBST(node.right);
}
这样写是有问题的，不能节点的值一定比左子树中的值都大，也不能保证比右子树中的值都小。原因是该代码只对节点与其左右节点的值做了约束。而我们需要把最上层的约束也加进去。
通过构造辅助函数，增加参数，将根节点的约束加进去：
boolean isValidBST(TreeNode node){
return hlp(node, null, null);
}
// 辅助函数hlp
boolean hlp(TreeNode node, TreeNode min, TreeNode max){
if(node == null) return true;
if(min != null && node.val < min.val) return false;
if(max != null && node.val > max.val) return false;
return hlp(node.left, min, node) && isValidBST(node.right, node, max);
}
4.在BST中搜索一个数 LeetCode 700题： BST中搜索一个数
分析：利用二叉搜索树的性质，采用类似于二分查找的方法
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root == null) return null;
TreeNode node = null;;
if(val < root.val){
node = searchBST(root.left, val);
}else if(val == root.val){
node = root;
}else if(val > root.val){
node = searchBST(root.right, val);
}
return node;
}
}
5.在BST中插入一个数
分析：利用4中的框架，先找到要插入的位置，再插入。
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null){
return new TreeNode(val);
}
if(root.val == val){
return root;
}else if(root.val < val){
root.right = insertIntoBST(root.right, val);
}else{
root.left = insertIntoBST(root.left, val);
}
return root;
}
}
6.在BST中删除一个数 LeetCode 450题：删除BST中一个数
分析：要删除一个数首先要找到这个数，同样利用4中框架。找到之后，删除要分几种情况：
1 该节点无左右节点，直接删除即可；
2 该节点有右（左）节点，无左（右）节点，此种情况，用右（左）节点替换根节点即可；
3 该节点有左、右节点。此种情况，要保证删除节点后仍是BST，需在左子树中找到最大节点（或在右子树中找到最小节点），将其值赋给根节点，后删除最大（小）节点；
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null) return null;
if(root.val == key){
if(root.left == null){
return root.right;
}
if(root.right == null){
return root.left;
}
TreeNode lmax = getLMax(root.left);
root.val = lmax.val;
root.left = deleteNode(root.left, lmax.val);
}
if(root.val < key){
root.right = deleteNode(root.right, key);
}
if(root.val > key){
root.left = deleteNode(root.left, key);
}
return root;
}
private TreeNode getLMax(TreeNode node){
while(node.right != null){
node = node.right;
}
return node;
}
}
