Unique Binary Search Trees II
Unique Binary Search Trees II
Givenn, generate all structurally uniqueBST's(binary search trees) that store values 1...n.
For example,
Givenn= 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
confused what"{1,#,2,3}"
means?>
read more on how binary tree is serialized on OJ.
五星级难度指数吧。
如何处理结束条件?
如果构造所有二叉排序树?
把递归放进循环里面的思想——这样就可以抽离根节点和左右子树节点
熟记这个思想,难度指数可以降低到4星级。
思想十分难,程序构造处理并不复杂。
//2014-2-15 update AC
vector<TreeNode *> generateTrees(int n)
{
return gen(1, n);
}
vector<TreeNode *> gen(int left, int right)
{
if (left > right) return vector<TreeNode *>(1, nullptr);
vector<TreeNode *> rs;
for (int k = left; k <= right; k++)
{
vector<TreeNode *> lt = gen(left, k-1);
vector<TreeNode *> rt = gen(k+1, right);
for (int i = 0; i < lt.size(); i++)
{
for (int j = 0; j < rt.size(); j++)
{
TreeNode *n = new TreeNode(k);
n->left = lt[i];
n->right = rt[j];
rs.push_back(n);
}
}
}
return rs;
}
分享到:
相关推荐
LeetCode-BinarySearch
Pow(xn) leetcode Binary-Search-3 问题1 Pow(x,n) () 问题2 找到 K 个最近的元素 ()
Binary-Search-1 问题1 搜索二维矩阵() 问题1 在旋转排序数组中搜索 () 问题2 在无限排序数组中搜索: 给定一个未知长度的排序数组和一个要搜索的数字,返回该数字在数组中的索引。 越界访问元素会引发异常。 如果该...
704.Binary_Search二分查找【LeetCode单题讲解系列】
Programming Questions on BinarySearch, LeetCode, CodeChef
二分查找Binary_Search套路和解题模板【LeetCode刷题套路教程3】
Leetcode 92. 反转链表 II问题描述算法解法1: 递归图示解法1:实现def reverseBetween(self, head: ListNode
* [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]...
leetcode卡leetcode 二叉树卡片 LeetCode 二叉树卡片问题的章节智解
leetcode卡 leetcode 自己刷leetcode,然后记录下来。。。相当于打卡吧! (Unique Binary Search Trees需要用)
Binary-Search-3.1 问题1 优化航线 () 在尝试这个问题之前有 3 件事需要知道: maxTravelDist,它是一个整数,表示给定飞机的最大操作行程距离; forwardRouteList,它是一个整数对列表,其中第一个整数表示前向航线...
Binary-Search-2 问题一:() 给定一个按升序排序的整数 nums 数组,找到给定目标值的开始和结束位置。 您的算法的运行时复杂度必须为 O(log n)。 如果在数组中找不到目标,则返回 [-1, -1]。 示例 1: 输入:nums ...
leetcode的题目:Balanced Binary Tree
leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
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 二叉树的递归 ...
leetcode卡除非您已经使用过卡片,否则不要看这里。 做真实的自己!
leetcode求交集Binary-Search-4 问题1 两个数组的交集 II () 问题2 两个有序数组的中位数 ()
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)
作者: 负雪明烛个人博客: :