唯一二叉搜索树

版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~

• Unique Binary Search Trees
  Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
  For example,
  Given n = 3, there are a total of 5 unique BST's.

  
  

• 题目大意：给定一个数字n，有多少个结点值为1~n的唯一二叉搜索树？
  例如：给定n=3，共有5个二叉搜索树。

• 思路（递归）：二叉搜索树的性质，左边的数都比根小，右边的数都比根大。二叉树的节点是从1到n，所以能确定如果根为k，则根左边的数是1到k-1，根右边的数是k+1到n。对于一个根来说，唯一二叉树的数量是其左子树的数量乘以右子树的数量。也就是说，假如有n个结点，则唯一二叉搜索树的个数为f(n) = f(0)·f(n-1) + f(1)·f(n-2) + ... + f(n-1)·f(0)，意思是，当根节点为1的时候，左子树有0个，右子树有n-1个，相乘即得此时的唯一二叉树个数；当根节点为2的时候，左子树有1个，右子树有n-2个，相乘即得此时的唯一二叉树个数；以此类推，当最后根节点为n时，左子树有n-1个，右子树有0个，相乘即得此时的唯一二叉树个数。

• 代码（递归）

int numTrees(int n)
{
    if(n == 0)return 1;
    if(n == 1)return 1;
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        // 假设当前的根节点是i+1（从0开始，root结点值应该加一）
        // 则左子树有0~i个，右子树是（i+2）~n个
        res += numTrees(i) * numTrees(n-i-1);
    }
    return res;
}

• 思路（非递归）：还有一种是用动态规划的思想去做，理解了递归的思想，非递归的思想也就很好理解了，其实就是把递归改写成了循环，具体是把递归得到的数据存到一个一位数组中；时间复杂度O(N!)，空间复杂度O(N)。

int numTrees(int n) {
    int* res = new int[n+1];
    res[0] = 1;
    res[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        res[i] = 0;
        for(int j = 0; j < i; j++)
        {
            res[i] += res[j] * res[i-j-1];
        }//for
    }//for
    return res[n];
}

• 以上。

版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~