Unique Binary Search Trees
Givenn, how many structurally uniqueBST's(binary search trees) that store values 1...n?
For example,
Givenn= 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
动态规划法
本题关键:如何填表,如何得到计算公式.
需要很仔细画图,一步一步找出规律。
Catlan公式是可以计算这样的题目的,不过Catalan公式也不好理解,还是写个循环解决吧。
class Solution {
public:
int numTrees(int n)
{
vector<int> ta(n+1);
ta[0] = 1; ta[1] = 1; ta[2] = 2;
for (int i = 3; i <= n; i++)
{
int mid = (i-1)/2;
for (int j = 0; j < mid; j++)
{
ta[i] += ta[j] * ta[i-j-1] *2;
}
if (i%2) ta[i] += ta[mid] * ta[mid];
else ta[i] += ta[mid+1] * ta[mid] * 2;
}
return ta[n];
}
};
//2014-2-15 update
int numTrees(int n)
{
if (n < 3) return n;
int *A = new int[n+1];
A[0] = 1, A[1] = 1, A[2] = 2;
for (int i = 3; i <= n; i++)
{
int half = i/2;
A[i] = 0;//注意要初始化
for (int j = 1; j <= half; j++)
A[i] += A[j-1] * A[i-j] *2;//注意细节是+=
if (i%2 == 1) A[i] += A[half]*A[half];
}
return A[n];
}
//2014-2-15 update 2
int numTrees2(int n)
{
int *A = new int[n+1];
A[0] = 1;
for (int i = 1; i <= n; i++)
{
A[i] = 0;//注意要初始化
for (int j = 1; j <= i; j++)
A[i] += A[j-1] * A[i-j];//注意细节是+=
}
return A[n];
}
下面是参考资料:
http://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0
http://en.wikipedia.org/wiki/Catalan_number
分享到:
相关推荐
LeetCode-BinarySearch
Pow(xn) leetcode Binary-Search-3 问题1 Pow(x,n) () 问题2 找到 K 个最近的元素 ()
Binary-Search-1 问题1 搜索二维矩阵() 问题1 在旋转排序数组中搜索 () 问题2 在无限排序数组中搜索: 给定一个未知长度的排序数组和一个要搜索的数字,返回该数字在数组中的索引。 越界访问元素会引发异常。 如果该...
Programming Questions on BinarySearch, LeetCode, CodeChef
704.Binary_Search二分查找【LeetCode单题讲解系列】
二分查找Binary_Search套路和解题模板【LeetCode刷题套路教程3】
leetcode卡leetcode 二叉树卡片 LeetCode 二叉树卡片问题的章节智解
leetcode卡 leetcode 自己刷leetcode,然后记录下来。。。相当于打卡吧! (Unique Binary Search Trees需要用)
Binary-Search-3.1 问题1 优化航线 () 在尝试这个问题之前有 3 件事需要知道: maxTravelDist,它是一个整数,表示给定飞机的最大操作行程距离; forwardRouteList,它是一个整数对列表,其中第一个整数表示前向航线...
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
Binary-Search-2 问题一:() 给定一个按升序排序的整数 nums 数组,找到给定目标值的开始和结束位置。 您的算法的运行时复杂度必须为 O(log n)。 如果在数组中找不到目标,则返回 [-1, -1]。 示例 1: 输入:nums ...
leetcode的题目:Balanced Binary Tree
leetcode卡除非您已经使用过卡片,否则不要看这里。 做真实的自己!
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
Unique Binary Search Trees 本题参考了 里面的*How Many Binary Trees Are There?*章节。 The first few terms: C(0) = 1 C(1) = C(0)C(0) = 1 C(2) = C(0)C(1) + C(1)C(0) = 2 C(3) = C(0)C(2) + C(1)C(1)
leetcode求交集Binary-Search-4 问题1 两个数组的交集 II () 问题2 两个有序数组的中位数 ()
作者: 负雪明烛个人博客: :
leetcode python 001 Algorithm 用python和java解决了Leetcode上部分问题,另外还有对常规算法和机器学习算法的一些实现,例如用遗传算法解物流配送问题。...Search Trees Python 2017/11/28 Medium 09
leetcode 2 LeetCode 的二叉树 BinaryTree.py是一个方便的工具,它可以构建和显示编码时所需的二叉树 演示 您需要在使用之前导入该类 import BinaryTree as bt 从值/对象列表或二叉树构造二叉树 t1 = bt.BinaryTree...
Unique Binary Search Trees II Validate Binary Search Tree Convert Sorted Array to Binary Search Tree Convert Sorted List to Binary Search Tree LCA of BST Kth Smallest Element in a BST 二叉树的递归 ...