leetcode 96. Unique Binary Search Trees 卡特兰数：BST的数量 + 栈出栈数量

朱雀 2022-06-08 02:51 56阅读 0赞

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.

1 3 3 2 1  
\\ / / / \\ \\  
3 2 1 1 3 2  
/ / \\ \\  
2 1 2 3

这道题问的是可能构造的BFS二叉搜索树的数量，我是参考网上的教程做得。

这道题要求可行的二叉查找树的数量，其实二叉查找树可以任意取根，只要满足中序遍历有序的要求就可以。从处理子问题的角度来看，选取一个结点为根，就把结点 切成左右子树，以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积，所以总的数量是将以所有结点为根的可行结果累加起来。写成表达式如下：

熟悉卡特兰数的朋友可能已经发现了，这正是卡特兰数的一种定义方式，是一个典型的动态规划的定义方式（根据其实条件和递推式求解结果）。所以思路也很明确了，维护量res\[i\]表示含有i个结点的二叉查找树的数量。根据上述递推式依次求出1到n的的结果即可。

建议和这道题[leetcode 241. Different Ways to Add Parentheses 深度优先遍历DFS + 类似构造所有的二叉搜索树][leetcode 241. Different Ways to Add Parentheses _DFS _] 和 [leetcode 95. Unique Binary Search Trees II 递归构造所有可能的搜索二叉树BST + 卡特兰数][leetcode 95. Unique Binary Search Trees II _BST _] 一起学习

还有这一道题[leetcode 282. Expression Add Operators 任意添加运算符计算结果 +深度优先遍历DFS][leetcode 282. Expression Add Operators _ _DFS]

**若本题直接计算卡特兰数，你会发现Java十分容易越界，**超出了long的表示范围，所以我也没办法了。

**N个结点二叉树个数(不用卡特兰数求解）对于一个堆栈、若其入栈序列为1,2,3,……,n，不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数，且与不同形态的二叉树一一对应。**

关于卡特兰数，我建议记住这两个结论。

代码如下：

public class Solution 
    {
        //http://www.cnblogs.com/ccsccs/articles/4204677.html 
        /*
         * 这 道题要求可行的二叉查找树的数量，其实二叉查找树可以任意取根，只要满足中序遍历有序的要求就可以。
         * 从处理子问题的角度来看，选取一个结点为根，就把结点 切成左右子树，以这个结点为根的可行二叉树数量
         * 就是左右子树可行二叉树数量的乘积，所以总的数量是将以所有结点为根的可行结果累加起来。写成表达式如下：
         * 
         * 熟悉卡特兰数的朋友可能已经发现了，这正是卡特兰数的一种定义方式，是一个典型的动态规划的定义方式
         * （根据其实条件和递推式求解结果）。所以思路也很明确了，维护量res[i]表示含有i个结点的二叉查找树
         *  的数量。根据上述递推式依次求出1到n的的结果即可。 
         *  
         *  若本题直接计算卡特兰数，你会发现Java十分容易越界，超出了long的表示范围，所以我也没办法了。
         *  
         * N个结点二叉树个数(不用卡特兰数求解）
         * 对于一个堆栈、若其入栈序列为1,2,3,……,n，不同的出入栈操作将产生不同的出栈序列。
         * 其出栈序列的个数正好等于结点个数为n的二叉树的个数，且与不同形态的二叉树一一对应。
         * */
        public int numTrees(int n) 
        {
            if(n<=0)
                return 0;
            /*
             * 卡特兰数
             * f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)
             * Think more: Catalan Number.
             * f(n) = C(2n, n) / (n + 1) = (2n)!/(n!*(n+1)!)
            */
            int []res=new int[n+1];
            res[0]=res[1]=1;
            for(int i=2;i<=n;i++)
            {
                for(int j=0;j<i;j++)
                {
                    res[i]+= res[j]*res[i-j-1];
                }
            }
            return res[n];
        }
    }

下面是C++的做法，就是求解一个卡特兰数

代码如下：

#include<iostream>
    #include <vector>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int numTrees(int n) 
        {
            if (n <= 0)
                return 0;
            vector<int> dp(n+1,0);
            dp[0] = dp[1] = 1;
            for (int i = 2; i <= n; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    dp[i] += dp[j] * dp[i - j - 1];
                }
            }
            return dp[n];
        }
    };

[leetcode 241. Different Ways to Add Parentheses _DFS _]: http://blog.csdn.net/jackzhang_123/article/details/78092468
[leetcode 95. Unique Binary Search Trees II _BST _]: http://blog.csdn.net/jackzhang_123/article/details/77948273
[leetcode 282. Expression Add Operators _ _DFS]: http://blog.csdn.net/jackzhang_123/article/details/78119663