Unique Binary Search Trees Problem
Given n, how many structurally unique BSTs (binary search trees) that store values 1...n?
ExampleGiven 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 3Note
DP
Solutionpublic class Solution { public int numTrees(int n) { int[] count = new int[n+1]; count[0] = 1; for (int i = 1; i <= n; i++) { for (int root = 1; root <= i; root++) { int left = count[root-1]; int right = count[i-root]; count[i] += left*right; } } return count[n]; } }Unique Binary Search Trees II Problem
Given n, generate all structurally unique BST"s (binary search trees) that store values 1...n.
ExampleGiven 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 3Note
DFS
Solutionclass Solution { public ListgenerateTrees(int n) { if (n == 0) return new ArrayList<>(); return helper(1, n); } private List helper(int start, int end) { List res = new ArrayList<>(); if (start > end) { res.add(null); return res; } for (int i = start; i <= end; i++) { List left = helper(start, i-1); List right = helper(i+1, end); for (TreeNode leftNode: left) { for (TreeNode rightNode: right) { TreeNode root = new TreeNode(i); root.left = leftNode; root.right = rightNode; res.add(root); } } } return res; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65702.html
摘要:在这里我们使用数组中下标为的位置来记录个元素可以组成的平衡二叉树的数量。在递归的过程中,我们找到以当前节点作为根节点的所有平衡二叉树,并将结果以形式返回上一级调用。 题目要求 Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example, Gi...
摘要:而根可以选择从到的任意的数,唯一二叉树的总数,就是根为到的树相加。所以该问题化简为以为根,其唯一左子树和右子树各有多少,这就是个动态规划的问题了。 Unique Binary Search Trees I && II 解法请见:https://yanjia.li/zh/2019/02/... Given n, how many structurally unique BSTs (b...
摘要:题目解读穷举列出所有二叉树的结构类型。重点动态规划,关注临近,,之间的关系应用穷举组合,动态规划穷举组合,适用于相邻元素有规律。处注意边界值的情况。不能有重复,遗漏。 题目解读: 穷举列出所有二叉树的结构类型。重点: 动态规划,关注临近root,left,right之间的关系应用:穷举组合,动态规划穷举组合,适用于相邻元素有规律。bug处:注意边界值的情况。不能有重复,遗漏。 clas...
Unique Binary Search TreesGiven n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example,Given n = 3, there are a total of 5 unique BSTs. 1 3 3 ...
摘要:在线网站地址我的微信公众号完整题目列表从年月日起,每天更新一题,顺序从易到难,目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目,语言 JavaScript。 在线网站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公众号: showImg(htt...
阅读 3896·2021-11-23 10:09
阅读 1287·2021-11-23 09:51
阅读 2910·2021-11-23 09:51
阅读 1530·2021-09-07 09:59
阅读 2286·2019-08-30 15:55
阅读 2217·2019-08-30 15:55
阅读 2893·2019-08-30 15:52
阅读 2501·2019-08-26 17:04