构建二叉搜索树

前言

二叉搜索树是二叉树的一种特殊情况，我个人的理解二叉搜索树就是把二分查找树形化了，虽然这种定义不准确，但是二叉搜索树确实是二分查找的一种实现。

二分查找是有序数组的一种快速寻值的方式，目标值记为targetNum，随便找到数组中的某一个点，开始寻找，如果当前indexNum比targetNum大，就往左边找，如果比targetNum小，就往右边走。

二叉搜索树也是同样，如果根节点比targetNum大，就往左子树找，如果比targetNum小就去右子树寻找。这就是二叉搜索树的一个直接用法。

看一下二叉搜索树的定义及其性质

二叉搜索树(Binary Search Tree)，又名二叉排序树(Binary Sort Tree)。
二叉搜索树是具有有以下性质的二叉树：
1、若左子树不为空，则左子树上所有节点的值均小于或等于它的根节点的值。
2、若右子树不为空，则右子树上所有节点的值均大于或等于它的根节点的值。
3、左、右子树也分别为二叉搜索树。
4、二叉搜索树的中序遍历结果，就是二叉搜索树所有节点从小到大排序结果。

接下来，就用一道简单的题目来深刻理解一下儿茶搜索树

//给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？ 
//
// 示例: 
//
// 输入: 3
//输出: 5
//解释:
//给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
//
//   1         3     3      2      1
//    \       /     /      / \      \
//     3     2     1      1   3      2
//    /     /       \                 \
//   2     1         2                 3 

这道题其实是套了二叉树壳子的动态规划题目，首先分析一下题目

根据二叉搜索树的性质，我们知道，如果要构建一颗二叉搜索树，那么必须满足左子树的所有节点的值小于根节点的值，右子树所有节点的值大于根节点的值。

有了这两点依据，我们尝试用归纳法来处理一下。

如果n=1，那么只有一个元素，排列方式也只有一种。
如果n=2，那么有两种情况，1是2的左子树，或者2是1的右子树。

到这里停留一下，在n=2的时候我们还可以用另外一种思路来想，如果把1当成根节点，那么1的右侧只有2一个元素，根据n=1是排列结果count是1我们知道，如果把1当做根节点，右侧元素的组合只有1中，1左侧没有元素即为空树，空树的排列结果也是1，所以根节点选为1，得到的组合数就是

1（左边空树的排列结果）*1（右侧只有一个元素的排列结果） = 1

好，我们继续

如果n=3，排列的总数等于把1当根节点的总数，加上把2当根节点的总数，加上把3当根节点的总数之和；即
root1Count：1（左边空树的排列结果）2（右侧2个元素的排列结果） = 2
root2Count：1（左边1个元素的排列结果）1（右侧1个元素的排列结果） = 1
root3Count：2（左边2个元素的排列结果）*1（右侧空树的排列结果） = 2

由此类推，我们可以找到动态规划的状态转移公式

f(n) = nf(n-1) + (n-1)f(n-2)*f(1)+(n-2)f(n-3)f(2)....

由此我们可以编写代码

class Solution {

    // 记录排列结果
    private static Map<Integer, Integer> num2CountMap = new HashMap<>();
    
    public static int numTrees(int n) {
        // 空集的排解结果集数量为1
        num2CountMap.put(0, 1);
        for (int i = 1; i <= n; i++) {
            // 如果n=1 排列结果集数量为1
            if (i == 1) {
                num2CountMap.put(i, 1);
                continue;
            }
            // 如果n=2 排列结果集数量为2
            if (i == 2) {
                num2CountMap.put(i, 2);
                continue;
            }
            // 如果n>2,根据状态转移进行处理
            num2CountMap.put(i,getCount(i));
        }
        // 从排列结果map集合中获取结果
        return num2CountMap.get(n);

    }

    private static int getCount(int n) {
        int count = 0;
        // 计算状态转移后的结果
        for (int i = 1; i <= n; i++) {
            // 每一个点计算 左边元素的排列结果*右边元素的排列结果
            count+= num2CountMap.get(i-1)*num2CountMap.get(n-i);
        }
        return count;
    }

}