用ps做网站,绍兴金圣建设有限公司网站,网站构建工具,wordpress修改分类标题/*这道题的关键是#xff1a;动态表尽量的选取#xff0c;知道二叉搜索树中左子树的点都比根节点小#xff0c;右子树的点都比根节点大所以当i为根节点#xff0c;左子树有i-1个点#xff0c;右子树有n-i个点#xff0c;左右子树就可以开始递归构建#xff0c;过程和一开… /*这道题的关键是动态表尽量的选取知道二叉搜索树中左子树的点都比根节点小右子树的点都比根节点大所以当i为根节点左子树有i-1个点右子树有n-i个点左右子树就可以开始递归构建过程和一开始的过程是一样的而左右子树的特征中可以知道的就是点的个数所以用点的个数作为动态变量就很好。这样就给我们提供了一个思路动态规划和树结合的题由于子问题就是左右树所以动态变量的选取基本就是考虑题目给出的信息中可以从根节点得到左右子树的哪些特征用这个特征作为动态变量。二叉搜索树中都是左子树的点小于根节点右子树的点大于根节点对于所有子树都是这样。用dp[i]表示有i个数的时候能组成多少树dp[i] dp[0]*dp[i-1] ... dp[i-1]*dp[0]等号右边分别代表1到i分别是根节点的情况*/int[] dp new int[n1];dp[0] 1;//当没有节点时就只有一种情况for (int i 1; i n1; i) {for (int j 0; j i; j) {dp[i] dp[j] * dp[i-j-1];}}return dp[n]; 1 public ListTreeNode generateTrees(int n) {2 /*3 从i到n依次选取做为根节点生成一棵树.根节点为i的这个过程我们叫做function(i)则functioni中左子树就是从1到i-1的4 生成过程右子树就是从i1到n的过程递归function就行然后对左右子树就行全匹配就行5 */6 if (n 1)7 return new ArrayListTreeNode();8 return build(1, n);9 }
10
11 public ListTreeNode build(int start, int end) {
12 ListTreeNode res new ArrayList();
13 if (start end)
14 {
15 res.add(null);
16 return res;
17 }
18 for (int i start; i end; i) {
19 ListTreeNode left build(start, i - 1);
20 ListTreeNode right build(i 1, end);
21
22 for (TreeNode lt :
23 left) {
24 for (TreeNode rt :
25 right) {
26 //由于每次组合都形成一个新的树所以新建树应该是在这里
27 TreeNode root new TreeNode(i);
28 root.left lt;
29 root.right rt;
30 //注意添加的位置每组合一个左右子树就会形成一种情况
31 res.add(root);
32 }
33 }
34
35 }
36 return res;
37 } 转载于:https://www.cnblogs.com/stAr-1/p/7922877.html
