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.
13321 \/// \\ 3211 32 //\\ 2123
题意：给定n，，求出结点取值在1->n的二叉搜索树所有表示
解决思路：思路和之前的差不多，只不过为了生成树，需要用动态规划来生成子树
代码：
““java public class Solution { public List generateTrees(int n) { List[] result = new List[n + 1]; result[0] = new ArrayList(); result[0].add(null);
for(int i = 1; i <= n; i++){result[i] = new ArrayList<TreeNode>();for(int j = 0; j < i; j++){for(TreeNode nodeL : result[j]){for(TreeNode nodeR : result[i – j – 1]){TreeNode node = new TreeNode(j + 1);node.left = nodeL;node.right = clone(nodeR, j + 1);result[i].add(node);}}}}return result[n];}private TreeNode clone(TreeNode node, int offset){if(node == null){return null;}TreeNode temp = new TreeNode(node.val + offset);temp.left = clone(node.left, offset);temp.right = clone(node.right, offset);return temp;}
} “`
坦然接受生活给你的馈赠吧，不管是好的还是坏的。
