Leetcode 96.不同的搜索二叉树

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3

输出: 5

解释:

给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1

    \       /     /      / \      \

     3     2     1      1   3      2

    /     /       \                 \

   2     1         2                 3
 这道题仔细想其实很简单的。首先我们先得明白什么是二叉搜索树，二叉搜索树又称二叉查找树，二叉排序树，它或者是一棵空树，或者是具有下列性质的二叉树: 若它的左子树不空，
则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

解决这道题用两个函数：
1. G(n); 表示给定整数n的二叉搜索树的长度。其中G(0)=G（1）=1；
2. F（i,n）; 表示以i为根节点，数列长度为n的数列能构成不同二叉树的个数;

因为一个数列，如果它的根节点确定了，那么能构成它的不同二叉搜索树的左右节点个数也就确定了。G(n)= F(1,n)+F（2,n）+...+F（n,n）。例如求G(8),其中一个以3为根节点的数列其左子树数为G(3-1)；右子树数为4,5,6,7,8，
右子树的算法情况与1,2,3,4,5是一样的，所以右子树个数为G（n-3）,可得F(i,n)=G(i-1)*G（n-i);所以G(n)=G（0）*G（n-1）+...+G(n-1)*G(0);由此可看出其实这个G(n)就是卡特兰数,关于卡特兰数具体特点，如果不太了解
可以搜索研究一下 。所以有两个算法。

算法一：动态规则

public class Solution {

  public int numTrees(int n) {

    int[] G = new int[n + 1];

    G[0] = 1;

    G[1] = 1;

    for (int i = 2; i <= n; ++i) {

      for (int j = 1; j <= i; ++j) {

        G[i] += G[j - 1] * G[i - j];

      }

    }

    return G[n];

  }

}

算法二：利用数学公式

G(0)=G(1)=1; G（n+1）=2(2n+1)G（n）/(n+2)

class Solution {

public:

    int numTrees(int n) {

        long G = 1;

        for(int i = 0; i < n; i++)

            G= G * 2 * (2 * i  + 1) /(i + 2);

        return G;

    }

};

巴特西

Leetcode 96.不同的搜索二叉树

最新文章

热门文章