LeetCode96. 不同的二叉搜索树

题目描述

 /**
     * 
     * 给你一个整数 n ，
     * 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？
     * 返回满足题意的二叉搜索树的种数。
     * 
     */

思路分析

1. 对于数组中按照升序排列的元素，用这个数组组成一颗二叉搜索树，那么二叉搜索树的种类只于数组中元素的个数有关，而与数组中的元素无关，只要保证升序即可
2. 因此此题可以使用动态规划的思路，定义一个数组保存从1到n个元素对应的二叉搜索树的种类，已知n为0和1时二叉树的种类的1，大于1的情况，动态的改变
3. 对于n个数，因为这1到n个数都可以作为二叉搜索树的根节点，因此需要对其遍历一遍，然后不论以哪个数字作为根节点，都会产生左右子树的情况，因此还需要一个变量对当前作为根节点的数字的左右子树进行划分
4. 左右子树对应的二叉搜索树的种类也只和左右子树的个数有关，直接从数组中取出即可，然后对左右子树取笛卡尔积，得到的结果就是当前数字对应的二叉搜索树的种类，然后存入数组对应的位置
5. 依次执行上述步骤，直到n为止，然后将数组中n下标对应的数字返回，就是需要的结果
6. 源码见下

源码及分析

 public int numTrees(int n) {
        //数组res存储n个节点对应的二叉搜索树的种类，比如n为1时，只有一种
        int[] res = new int[n + 1];
        res[0] = 1;
        res[1] = 1;
        //动态的将n之间的所有的二叉搜索树的种类全部存储到集合
        for (int i = 2; i <= n; i++) {
            //以i为根节点时，将其以j分为左右两颗子树
            for (int j = 1; j <= i; j++) {
                //将i为根节点的所有情况加起来
                res[i] += res[j - 1] * res[i - j];
            }
        }
        return res[n];
    }