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
递归:
/* 设count[1,n]表示1~n可以组成的BST的个数。 num[i] 表示以i为根的BST个数,有num[i] = count[1,i-1]*count[i+1,n]; count[1,n] = sum(num[i]); */ public class Solution { public int numTrees(int n) { // Start typing your Java solution below // DO NOT write main() function if(n<1) return 0; return count(1,n); } public int count(int start,int end){ if(start == end) return 1; int count = count(start+1,end); count = count+count(start,end-1); for(int i = start+1;i<=end-1;i++){ count = count+count(start,i-1)*count(i+1,end); } return count; } }
Unique Binary Search Trees II
Aug 27 '123664 / 10952
Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 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
与上题相比,需要输出所有符合条件的树的具体形式:
/*集合的笛卡尔乘积*/ public class UniqueBinaryTree2 { public ArrayList<TreeNode> generateTrees(int n) { // Start typing your Java solution below // DO NOT write main() function return generateTrees(1,n); } public ArrayList<TreeNode> generateTrees(int start,int end){ ArrayList<TreeNode> result = new ArrayList<TreeNode>(); if(start>end) {result.add(null);return result;} for(int i = start;i<=end;i++){ ArrayList<TreeNode> lefts = generateTrees(start,i-1); ArrayList<TreeNode> rights = generateTrees(i+1,end); for (int j = 0; j < lefts.size(); ++j) { for (int k = 0; k < rights.size(); ++k) { TreeNode root = new TreeNode(i); root.lchild = lefts.get(j); root.rchild = rights.get(k); result.add(root); } } } return result; } }
相关推荐
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 二叉树的递归 ...