引子：五分钟玩转面试考点-数据结构系列，不会像那种严肃、古板的教科书般的博客文章，而是将晦涩难懂的概念和知识点尽可能幽默的细说出来，或结合生活场景，或从零开始分析。带给大家一个严肃而不失风趣的数据结构。
咱们就从一段话来开始今天的学习吧：
人事小R：小左同学，听说你搬家了？
小左同学：是的，因为我的孩子出生了...balabala
人事小R：停停...我不想听这些，你把最新地址给我一下就好了。
小左同学：知道了。(内心：mmp)
上面这段话什么意思呀？不要着急，咱们开始今天的学习，二叉搜索树。
首先，我要给大家推荐一款神器，(PS：小胖大学没学好数据结构，就是因为没遇到它，哼~) 搬运工小胖——图形化数据结构工具
1. 什么叫做二叉搜索树
二叉搜索树（BST,Binary Search Tree）也称为二叉排序树或者二叉查找树。
二叉搜索树：一棵二叉树，可以为null，但是不为null的情况下，需要满足：
-
非空左子树的所有键值小于其根节点的键值； -
非空右子树的所有键值大于其根节点的键值； -
左、右子树都是二叉搜索树。
[小胖友情提醒：二叉搜索树的中序遍历为有序的（升序）]
如下图：
2. 二叉搜索树常用算法
这里先说一下，小胖遇到的坑：小胖不想写递归代码，无非就是两个原因：
- 返回结果：在我查找到
结果之后，我不知道，要怎么结束递归，或者说，怎么把正确的值返回给用户。- 参数条件：我也不是很清楚如何将
参数值精确的传递到第n个方法中。
小胖冒着挨喷的风险，小心翼翼的把自己的总结贴出来（也就是针对上面这个问题的解决方案）：
-
递归返回值：也不是
无根之水。递归出口，就是在极端情况下的返回值，我们需要做的，就是让他在某一处返回我们需要的值，然后被上一个方法处理，或者直接返回给上上方法。而对于作为调用者来说，我并不关注你们底层的逻辑，我调用方法，我就想获取到最终结果。 -
递归参数：这里对说一次
值传递和引用传递。也有大神说都是值传递，这里咱们都不讨论了。Integer到底是值传递还是引用传递？小胖遇到的坑就是这个，开始方法的参数是int类型，但是递归调用的时候，会修改这个值，于是我就想将int转换为Integer类型。这样我就可以在后续的递归中每次都获取处理后的最新对象（美滋滋）。但是事实是残酷的，方法参数传递的Integer类型的参数，经过方法内处理之后，方法外没有变化！
2.1 二叉排序树的插入
二叉排序树的插入，我们是在根节点出发，若是比根节点小，左子树结构发生变化。若是比根节点大，那么右子树结构发生变化。
我（Root节点）并不关心，你发生了什么变化，只需将最新的地址赋予我就可以了。
/**
* 二叉排序树 插入算法
* root：我比左子树最右的字段都要大，比右子树最左的字段都要大
* key：我比你小，我要去你左边。
* root：我知道你们要做出修改，我不关心你到底修改了啥。但是，你把最新地址给我下吧。
* left：好哒
* right：好哒
*
* @param root
* @param val
* @return
*/
public TreeNode insertIntoBST(TreeNode root, int val) {
//极致情况
if (root == null) {
return new TreeNode(val);
}
//开始逻辑，想要插入到那个节点里面
//左子树(执行方法的后果：结构将被修改，但是我并不关心，我只要后续节点给我最新的地址。)
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}
2.2 二叉排序树的查找
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
这道题咱们应该怎么分析，查找第K个最小的元素。中序遍历 返回的是有序的数据集合。嗯，就用它 (我们的英雄小哪吒)。
什么，不是太了解 二叉树的遍历？那你必须来这了解一波了。名侦探小胖——花式遍历二叉树
总结来说，即使人之路径，根之输出。中序遍历是第二次获取根对象。去操作根对象。这里咱们采用的是栈，进栈的时候第一次操作对象，出栈的时候第二次操作对象，在出栈的时候，判断是否到达次数。
//搜索第k小的元素
//你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
public int kthSmallest(TreeNode root, int k) {
//中序遍历有序的，倒数第K个元素，即第几次完成中序遍历（栈）
//入栈是第一次操作元素，将数据入栈
Stack<TreeNode> stack = new Stack<>();
int data = -1;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
//第一次操作对象
root = root.left;
}
//若是栈中有数据
if (!stack.empty()) {
root = stack.pop();
//第二次操作对象
k--;
if (k == 0) {
data = root.val;
break;
}
root = root.right; //取出最左元素
}
}
return data;
}
2.3 二叉排序树的删除
二叉树删除比较复杂，这里咱们需要考虑几种情况：
- 没有节点时，直接将
该节点删除；- 1个子树的情况下，删除节点就是，该节点的
父节点指向孙子节点；- 2个子树的情况下：
- 先将左子树的最右节点，或者右子树的最左节点（仅此于根节点大小的节点）替换根节点（本质是：删除根节点）。
- 然后，删除左子树的最右节点（
即：替换根节点的节点）。(我们需要注意的是：一个节点若是最右节点，那么他一定没有右子树)。可以将其规划为情况1或者情况2进行删除；
咱们就分析下，如何递归写出来吧
- 首先要处理极端情况下的返回值，即
root==null时； - 作为
调用者的我们，并不关心结构到底如何修改，要是我的左子树发生改变。那么只需将变化后的位置给我就可以了（各扫门前雪）。右子树同上。 - 要是我（
Root节点）要被删除，那么我就需要考虑，若是我的左子树为空那么我将右子树返回，或者右子树为空，我将左子树返回。返回的是新的地址。我直接返回给调用者新的数据结构地址就可以了。（可以想下，2个节点，删除父节点，返回的结果，就是左子树或者右子树地址。一个节点，删除该节点，直接返回null） - 要是删除节点含有左右子树。我们需要执行下面几步：
4.1 保存父节点信息；TreeNode tempMode = root;
4.2 定位到父节点左子树；root = root.left;
4.3 定位左子树的最右节点；while (root.right != null)
4.4 最右节点替换父节点；tempMode.val = root.val;
4.5 删除最右节点，本质上就是根节点（tempMode）左子树（左子树结构发生变化）删除节点值为key的数据。tempMode.left = deleteNode(tempMode.left, root.val);继续递归。
4.6 将临时根节点（tempMode）信息保存到root节点中。
public static TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
//操作左子树
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
//找到的情况,第1,2种情况
if (root.left == null) {
root = root.right;
} else if (root.right == null) {
root = root.left;
} else {
//1. 保存将要删除的根节点坐标
TreeNode tempMode = root;
//2. 我们的操作本质是在左子树上找到最右元素
//2.1 定位左子树
root = root.left;
//2.1 定位左子树最右元素
while (root.right != null) {
root = root.right;
}
//3. 元素替换（删除根元素）
tempMode.val = root.val;
//4. 删除替换根元素的节点
//问题？root tempNode的左子树中，（一棵树中，删除节点key）
tempMode.left = deleteNode(tempMode.left, root.val);
root = tempMode;
}
}
return root;
}
递归方法到底怎么书写：比较难捉摸的就是返回值。首先在我写这个方法之前，已经这个
方法本质已经存在了，且调用方法一定会返回给我一个（我想要）结果，我无需关注其内部的逻辑处理。我只需关注本次方法如何处理。
