二叉搜索树（BST）

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;
    }
}