鹰潭网站商城建设,无锡网络优化推广公司,天津市津南区教育网站建设招标,品牌微营销网站建设力扣labuladong一刷day36天
一、96. 不同的二叉搜索树
题目链接#xff1a;https://leetcode.cn/problems/unique-binary-search-trees/ 思路#xff1a;这是一道典型的动态规划题#xff0c;从n3来看 子树有几种形态 (0, 2)、(1, 1)、(2, 0)有规律可循#xff0c;即为左…力扣labuladong一刷day36天
一、96. 不同的二叉搜索树
题目链接https://leetcode.cn/problems/unique-binary-search-trees/ 思路这是一道典型的动态规划题从n3来看 子树有几种形态 (0, 2)、(1, 1)、(2, 0)有规律可循即为左子树为0的种数*右子树为2的种数 左子树为1的种树 * 右子树为1的种树 左子树为2的种数 * 右子树为0的种数。定义dp数组表示dp[i]为ni时二叉搜索树的种数递推公式dp[i]dp[j]*dp[i-j-1] (in, j i)初始化dp[0]1, dp[1]1, dp[2]2;
class Solution {public int numTrees(int n) {if (n 1) return 1;int[] dp new int[n1];dp[0] 1;dp[1] 1;dp[2] 2;for (int i 3; i n; i) {for (int j 0; j i; j) {dp[i] dp[j] * dp[i - j -1];}}return dp[n];}
}二、95. 不同的二叉搜索树 II
题目链接https://leetcode.cn/problems/unique-binary-search-trees-ii/ 思路
class Solution {public ListTreeNode generateTrees(int n) {if (n 0) return new ArrayList();return build(1, n);}ListTreeNode build(int lo, int hi) {ListTreeNode res new LinkedList();// base caseif (lo hi) {res.add(null);return res;}// 1、穷举 root 节点的所有可能。for (int i lo; i hi; i) {// 2、递归构造出左右子树的所有有效 BST。ListTreeNode leftTree build(lo, i - 1);ListTreeNode rightTree build(i 1, hi);// 3、给 root 节点穷举所有左右子树的组合。for (TreeNode left : leftTree) {for (TreeNode right : rightTree) {// i 作为根节点 root 的值TreeNode root new TreeNode(i);root.left left;root.right right;res.add(root);}}}return res;}
}
