性质

二叉搜索树：左子树 < 节点 < 右子树（注意，左子树所有节点都要小于根节点，而不仅仅是左节点）

核心知识：二叉搜索树的中序遍历序列是升序的。

查找节点

跟二分法类似，如果要查找的值比 curr 小，那么在左子树找，如果大，那么在右子树找

插入节点

从 root 节点开始， 一直循环查找，直到 curr 为 null 为止。

循环逻辑就是查找节点的逻辑。

注意在循环过程中要启临时变量 pre 来记录父节点，以便在循环结束后在父节点进行插入。

二叉搜索树不允许重复值，如果找到重复值直接返回。

删除节点

分三种情况讨论：

情况1：如果要删除的节点没有子节点，那么直接删除即可

parent.left= null （ 或 parent.right = null ）

情况2：如果要删除的节点只有一个子节点，那么将其子节点替换为它即可

parent.left = curr.left （或者 right）

情况3：如果要删除的节点有两个子节点 ，则不可以直接删除，要让待删除节点的【左子树的最大节点】 或 【右子树的最小节点】 替换它，替换步骤如下：

1. 查找要删除的节点 cur
2. 找到 cur 在中序遍历的下一个节点 nex （也就是它的右子树的最左叶子）

TreeNode nex = cur.right;
while (nex.left != null) {
    tmp = tmp.left;
}

3. 用 nex 的值覆盖待删除节点的值，并在树中递归删除节点 nex

// 递归删除节点 nex 
remove(nex .val);
// 用 nex 覆盖 cur
cur.val = nex .val;