二叉搜索树的定义及性质
定义
二叉搜索树（Binary Search Tree BST）是一种特殊的二叉树, 又称为排序二叉树，二叉查找树，二叉排序树。二叉查找树的递归定义如下：
- 要么二叉搜索树是一颗空树
- 要么二叉搜索树是由根节点，左子树，右子树组成，其中左子树和右子树都是二叉搜索树，且若左子树不空，左子树上所有节点的数据域 均小于 根节点的数据域，若右子树不空，则右子树上所有节点的数据域 均大于 根节点的数据域。
性质
二叉搜索树的一个实用的性质就在于：对二叉搜索树进行中序遍历，遍历的结果是有序的。
这是由于二叉搜索树本身的定义就包含了 左子树< 根节点 < 右子树 的特点，而中序遍历的顺序就是 左子树 → 根节点→ 右子树，因此，所得到的中序遍历序列是有序的。
二叉搜索树相关习题。
1. 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
解法
由于二叉搜索树中序遍历得到的结果是有序的，那么就可以对这棵树进行中序遍历，中序遍历的顺序就是 左子树 → 根节点 → 右子树。所以在遍历的过程中，我们需要记录前一个节点 pre ，并且比较这两个节点的数据 cur ，如果 pre 的数据域中的值大于 cur,则说明这不是一棵 二叉搜索树。
public class Solution98 {
TreeNode pre;
public boolean isValidBST(TreeNode root) {
if(root==null){
return true;
}
boolean isLeft= isValidBST(root.left);
if(!isLeft){
return false;
}
if(pre!=null&&pre.val>=root.val){
return false;
}
pre=root;
boolean isRight=isValidBST(root.right);
return isRight;
}
}
2.二叉搜索树的最小绝对差
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
解法
这题和上一题的解法类似，二叉搜索树的中序遍历是有序的，那么求两节点的差的绝对值的最小值，只需要 求相邻两个节点的差值，并维护就可以了。
TreeNode pre;
int result =Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
travsel(root);
return result;
}
public void travsel(TreeNode root){
if(root==null){
return ;
}
travsel(root.left);
if(pre!=null){
result=Math.min(result,root.val- pre.val);
}
pre=root;
travsel(root.right);
}
3. 二叉搜索树中的众数
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
暴力法
对于二叉搜索树，可以进行一次中序遍历，保存遍历得到的序列结果，再次对 序列进行遍历，用 hashMap 保存对应的结果，取最大值。再次遍历一次 hashmap 即可。
public List<Integer> path=new ArrayList<>();
public int[] findMode(TreeNode root) {
inTravsel(root);
HashMap<Integer,Integer> cnt=new HashMap<>();
for(int i=0;i<path.size();i++){
cnt.put(path.get(i),cnt.getOrDefault(path.get(i),0)+1);
}
int maxValue=0;
for(Integer key: cnt.keySet()){
int nowValue=cnt.get(key);
if(nowValue>maxValue){
maxValue=nowValue;
}
}
List<Integer> res=new ArrayList<>();
for(Integer key: cnt.keySet()){
if(cnt.get(key)==maxValue){
res.add(key);
}
}
int [] res1=new int[res.size()];
for(int i=0;i<res.size();i++){
res1[i]=res.get(i);
}
return res1;
}
public void inTravsel(TreeNode root){
if(root==null){
return ;
}
inTravsel(root.left);
path.add(root.val);
inTravsel(root.right);
}
利用二叉树的性质
我们知道二叉搜索树的中序遍历序列是有序的，那么可以从头遍历，取相邻两个元素做比较，把出现频率最高的元素输出就可以了。
在树上的找相邻的两个元素，那么需要一个 pre 指针指向 前一个节点，来与现在的 节点 cur 频率作比较,用 nowCount 来记录当前元素的数量，maxCount 记录当前众数的个数，result 记录所有的众数的值。在中序遍历的过程中进行维护更新 nowCount ,同时与maxCount 作比较。注意在 nowCount > maxCount时，不仅仅是对 maxCount 进行更新，还要对 result进行清空处理。
class Solution {
int nowCount;
int maxCount;
TreeNode pre;
List<Integer> res;
public int[] findMode(TreeNode root) {
nowCount=0;
maxCount=0;
pre=null;
res=new ArrayList<>();
inTraversal(root);
int [] result= new int[res.size()];
for(int i=0;i<res.size();i++){
result[i]=res.get(i);
}
return result;
}
public void inTraversal(TreeNode cur){
if(cur==null){
return ;
}
inTraversal(cur.left);
if(pre==null){
nowCount=1;
}else if(pre.val==cur.val){
nowCount+=1;
}else{
nowCount=1;
}
if(maxCount==nowCount){
res.add(cur.val);
}
if(maxCount<nowCount){
res.clear();
maxCount=nowCount;
res.add(cur.val);
}
pre=cur;
inTraversal(cur.right);
return ;
}
}
4. 二叉搜索树的插入操作
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
解法
这题的话，可以简单的思考，新值和原始二叉搜索树种的任意节点都不同，那么可以简单的考虑，比较 root.val与要插入的值做比较，若是 root.val > val ,那么新的节点应该插入左子树中，此时，如果根节点的左子树为空，那么新的节点就是根的左子树；如果不为空，那么问题就转化成了向根节点的左子树中插入一个新的节点，所以，递归插入，右子树 同样应该如此判断。
[HTML_REMOVED]代码如下：[HTML_REMOVED]
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null){
return new TreeNode(val);
}
else{
insertNode( root,val);
return root;
}
}
public void insertNode( TreeNode node,int val){
if(node==null){
return;
}
if(node.val>val){
//向左子树插入
if(node.left==null){
node.left=new TreeNode(val);
return ;
}else{
insertNode(node.left,val);
}
}
else{
//向右子树插入
if(node.right==null){
node.right=new TreeNode(val);
return ;
}
else{
insertNode(node.right,val);
}
}
}
}
5. 删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
1. 首先找到需要删除的节点；
2. 如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
解法：
删除节点的情况比插入的要复杂，
这题，如果要删除的就是节点为 node ，那么判断情况：
node为null,那么可以直接返回空了，node不为null, 其左子树为空，但是右子树不为空，则用右子树作为根节点并返回。node不为null, 其右子树为空，左子树不为空，则用左子树作为根节点并返回。node不为null,其左右子树都是空，这个也简单，直接删除该节点，返回空。node及其左右子树都不为空，那么可以先处理左子树，左子树要作为右子树的最左边的叶子节点的左子树 ，这是由二叉搜索树的性质所决定的，再将右子树作为根节点返回。
如果根节点不符合条件，那么问题就转化成了在左右子树中删除相应的节点的相似情况，那就可以用递归处理了。
确定下递归的条件：
- 递归的参数以及返回值，参数自然是根节点 root ,以及对应的值key。返回值为新的根节点
- 确定终止条件：当遇到空节点 null时，就返回空，说明没有找到要删除的节点
- 确定单层递归的逻辑：也就对应上面的 5 层情况。
还有，递归的返回值是新的根节点，那么在本层次结束返回上一层时，上一层需要用相应的值接住，也就是 左子树，或者右子树。
public class Solution450 {
/**
* @param root
* @param key
* @return
* 返回值为 子树删除根节点的新的根节点
*/
public TreeNode deleteNode(TreeNode root, int key) {
// 1. 没有找到删除的节点，遍历到空节点直接返回
if(root==null){
return root;
}
/**
* 2. 3. 4.
* 左右子树都为空，那么直接删除，返回 null
* 左子树为空，右子树不为空，删除节点，右子树作为新的根节点返回
* 左子树不为空，右子树为空，删除节点，左子树作为新的根节点返回
*/
if(root.val==key){
if(root.left==null) return root.right;
else if(root.right==null) return root.left;
else{
/**
* 左右子树都不为空，
* 则先把 删除节点的左子树
* 作为 删除节点的右子树的最左边的叶子节点的左子树。
* 返回删除节点右子树为新的根节点。
*/
TreeNode cur=root.right; // 找右子树最左面的节点
// 把要删除的节点（root）左子树放在cur的左孩子的位置
while(cur.left!=null){
cur=cur.left;
}
cur.left=root.left;
root=root.right; // 返回旧root的右孩子作为新root
return root;
//这里的返回值就相当于把节点返回给上一层，上一层就需要对应的节点接住，是左子树，或者右子树
}
}
if(root.val>key){
//递归处理左子树，并且更新左子树的值。
root.left=deleteNode(root.left,key);
}
if(root.val<key){
root.right=deleteNode(root.right,key);
}
return root;
}
}
6. 将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
解法
由于二叉搜索树的中序遍历是有序数组这一性质，利用有序数组来构造二叉搜索树，那么根节点肯定就是数组的中位数。那么根节点确定了。那么数组中，位于根节点左边的部分就可以用来构建左子树，位于根节点右边的部分就可以用来构建右子树。这样的话，问题转化成了相应的子问题。用递归解决。
- 递归的参数及返回值：数组，以及对应的左右边界。
- 终止条件：确定了在[left,right] 这段区间内建树，那么当 left > right 时，返回空
- 本层次的递归逻辑：取数组中间位置的值来构建节点，再划分区间，左边区间用来构造左孩子，右边区间用来构造右孩子。最后返回根节点。
class Solution {
public TreeNode sortedArrayToBST(int[] nums){
return buildTree(nums,0,nums.length-1);
}
public TreeNode buildTree(int[] nums,int left,int right){
if(left>right) return null;
int mid=(left+(right-left)/2);
TreeNode root= new TreeNode(nums[mid]);
root.left=buildTree(nums,left,mid-1);
root.right=buildTree(nums,mid+1,right);
return root;
}
}
7. 把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
解法：
使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
原来是一棵二叉搜索树，那么中序遍历该树，得到一个有序序列，那么只需要做到与其后面所有的节点的值相加即可，也就是从最右边的节点开始，每一个节点的值都更新为自身节点与前一个节点的值的和。
也就说遍历的顺序是 右 -> 根 -> 左。也就是反的中序遍历，在遍历的过程中完成值的更新。
class Solution {
public int pre;
public TreeNode convertBST(TreeNode root) {
traversal(root);
return root;
}
public void traversal(TreeNode cur){
if(cur==null){
return ;
}
traversal(cur.right);
cur.val=pre+ cur.val;
pre=cur.val;
traversal(cur.left);
}
}
