首页 > 代码库 > Unique Binary Search Trees,Unique Binary Search Trees2 生成二叉排序树
Unique Binary Search Trees,Unique Binary Search Trees2 生成二叉排序树
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
算法分析：类似上阶梯，简单的动态规划问题。当根节点为i时，比i小的节点有i-1个，比i大的节点有n-i个，所以，i为根节点能够生成二叉排序树的个数是
nums[n] += nums[i-1]*nums[n-i]，i从1到n。
public class UniqueBinarySearchTrees{ public int numTrees(int n) { if(n <= 0) { return 0; } int[] res = new int[n+1]; res[0] = 1; res[1] = 1; for(int i = 2; i <= n; i ++) { for(int j = 1; j <= i; j ++)//j为根节点 { res[i] += res[j-1]*res[i-j]; } } return res[n]; }}Unique Binary Search Trees2：求生成二叉排序树的根节点的集合
Given an integer 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 UniqueBinarySearchTreesII { public List<TreeNode> generateTrees(int n) { if(n <= 0) { return new ArrayList<TreeNode>(); } return helper(1, n); } public List<TreeNode> helper(int m, int n) { List<TreeNode> res = new ArrayList<>(); if(m > n) { res.add(null); return res; } for(int i = m; i <= n; i ++) { //i为根节点 List<TreeNode> ls = helper(m, i-1);//i节点的左子树 List<TreeNode> rs = helper(i+1, n);//i节点的右子树 for(TreeNode l : ls) { for(TreeNode r : rs) { TreeNode curr = new TreeNode(i); curr.left = l; curr.right = r; res.add(curr); } } } return res; }}
Unique Binary Search Trees,Unique Binary Search Trees2 生成二叉排序树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。