二叉搜索树性质：
左子树所有节点都小于根节点，右子树所有节点都大于根节点
LeetCode 700. 二叉搜索树中的搜索
根据其性质，可很快写出搜索的代码如下：
public class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) return null;
if (root.val == val) {
return root;
} else if (root.val < val) {
return searchBST(root.right, val);
} else {
return searchBST(root.left, val);
}
}
}
LeetCode 98. 验证二叉搜索树
围绕二叉搜索树的性质来思考，如果每次递归，都规定好当前节点node的范围：min < node < max，那么我们是不是就能知道每个节点node在树中摆放的位置是否合规，从而验证一颗二叉搜索树。
所以在编写代码时，关键点在于对递归函数的定义，要加入min和max两个辅助参数，这样我们就可以对每一层节点的大小进行规约、判断。
具体代码如下：
public class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
/**
* in和max用于将最小、最大的约束一层层传递下去，
* 如果只是单纯判断根节点和左右子树的大小关系，是无法验证BST的
*
*@return
*/
private boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
if (root == null) return true;
if ((min != null && root.val <= min.val) || (max != null && root.val >= max.val)) return false;
return isValidBST(root.left, min, root) && isValidBST(root.right, root, max);
}
}
LeetCode 450. 删除二叉搜索树中的节点
删除二叉搜索树节点的操作稍微有点麻烦，如果要删除的节点是叶子节点，那么可以直接删除并返回，如果仅存在左子树或仅存在右子树也好办，我们返回存在的子树的根节点，让它来顶替目标节点即可，麻烦的是如果目标节点同时存在左、右两颗子树，那么我们就要考虑在删除目标节点后，如何维护左右子树，让这两颗子树仍然属于整颗二叉搜索树、并且仍然符合BST的性质？
我们要做的，就是要找到目标节点左子树中的最大节点或者目标节点右子树中的最小节点，让这两者中任意一个上来顶替当前目标节点，即可完成子树的重建，本题解用的是右子树中的最小节点；
代码逻辑如下：
1、如果要删除的目标节点的节点值<当前节点的节点值，说明目标节点在左子树中，于是往左子树中查找、删除，同时在删除完后返回最新的左子树，给到当前节点进行更新；
2、右子树同理；
3、如果当前节点就是目标节点，那么：
- 判断如果左子树为空，直接返回右子树；
- 同理，如果右子树为空，直接返回左子树；
- 如果都不为空，那么
- 找到右子树中最小的节点
- 将最小节点移除
- 当前节点替换为最小节点
具体代码如下：
public 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 minNode = findMin(root.right);
// 从右子树中删除找到的这个替换节点，同时返回并更新最新的右子树
root.right = deleteNode(root.right, minNode.val);
// 将最小节点替换为当前节点（直接root.val = minNode.val也可以，但不适用存储复杂结构的二叉搜索树）
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;
}
private TreeNode findMin(TreeNode node) {
while (node.left != null) node = node.left;
return node;
}
}
LeetCode 701. 二叉搜索树中的插入操作
这题唯一需要注意的是函数的定义，我们在下探到递归函数的下一层时，要时刻围绕这个函数定义来写代码。就比如下面代码中2、3处，在确定应该往左子树或者右子树插入后，我们还要将其返回的最新的左子树/右子树给更新到当前节点中，这一步如果不明确函数的定义，有时候可能会写漏了。。
具体代码如下：
public class Solution {
/**
* 重点在函数的定义：在二叉搜索树中找到节点适合插入的位置，插入节点并返回子树的根节点
*
*/
public TreeNode insertIntoBST(TreeNode root, int val) {
// 1、找到插入位置，直接新建一个节点返回
if (root == null) return new TreeNode(val);
// 2、比当前节点值小，那么往左边插入，并更新左子树
if (root.val > val) root.left = insertIntoBST(root.left, val);
// 3、比当前节点值大，那么往右边插入，并更新右子树
if (root.val < val) root.right = insertIntoBST(root.right, val);
return root;
}
}
