新博文地址:[leetcode]Unique Binary Search Trees
http://oj.leetcode.com/problems/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.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
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
刚拿到这道题,直觉是树,但是看了之后发现完全与树关系不大,是个很典型的DP问题:
比如说有1~n,n个节点,我们选择一个中间节点k为根节点,那么左子树就变成了子问题 1 ~ (k-1)有几种构造法,右子树就变成了(k + 1) ~ n有几种构造法,左子树跟右子树的组合数,就是n个节点的构造数;
即f(n) = sum{ f(k - 1) * f( n - k) | k = 1 ~ n }
容易知道f(0) = f(1) = 1; f(2) = 2;
接下来的编程就容易了:
public int numTrees(int n) { if(n <= 1){ return 1; } int[] num = new int[n + 1]; num[0] = 1; num[1] = 1; num[2] = 2; for(int i = 3; i <= n; i++){ for(int j = 1; j <= i; j++){ num[i] += num[j - 1] * num[i - j]; } } return num[n]; }
虽然AC,但是 时间复杂度略高,不知道有没有O(n)的解法
相关推荐
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 二叉树的递归 ...