[leetcode] 96. Unique Binary Search Trees

[leetcode] 96. Unique Binary Search Trees

Description

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

Input:

3

Output:

5

Explanation:

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

分析

题目的意思是：给定n，求出有多少个二叉查找树，其中二叉查找树的节点的值为1~n.

设dp[i]表示共有i个节点时，能产生的BST树的个数n == 0 时，空树的个数必然为1，因此dp[0] = 1n == 1 时，只有1这个根节点，数量也为1，因此dp[1] = 1因此，dp[2] = dp[0] * dp[1] + dp[1] * dp[0]n == 3时，构造方法如题目给的示例所示，dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0]同时，当根节点元素为 1, 2, 3, 4, 5, …, i, …, n时，基于以下原则的BST树具有唯一性：以i为根节点时，其左子树构成为[0,…,i-1],其右子树构成为[i+1,…,n]构成因此，dp[i] = sigma（dp[k] * dp[i-1-k]） 0 <= k < i - 1

代码

class Solution {public: int numTrees(int n) { if(n<0){ return -1; } vector dp(n+1,0); dp[0]=1; dp[1]=1; for(int i=2;i<=n;i++){ for(int j=0;j

参考文献

​​[编程题]unique-binary-search-trees​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。