Problem Description:
Given an integer n, generate all structurally unique BST‘s (binary search trees) that store values 1 ... n.
给定一个整数n，生成所有不同的二叉搜索树，其节点存储所有从1到n的值。
此题是96题的follow up，96题采用动态规划顺利接出来了，但是看到这个题时没有想到如何利用96题的动态规划的思路（没有想到clone的方法），碰壁了几次。
想到过按顺序插入值到二叉树中，但是这样会出现重复，例如n=3，按2，1，3和按2，3，1插入顺序会得到相同的结果，且重复问题难以解决。
可行的解法有递归的解法和动态规划（参考了huahuajiang的的博客https://zxi.mytechroad.com/blog/uncategorized/leetcode-95-unique-binary-search-trees-ii/）。
def gen(s, e): return [tree(i, l, r) for l in gen(s, i – 1) for r in gen(i + 1, e) for i in range(s, e+1)
时间复杂度O(n^3) 空间复杂度 O(n^3)
class Solution { public List<TreeNode> generateTrees(int n) { if(n == 0) return new ArrayList<>(); return generateTrees(1, n); } public List<TreeNode> generateTrees(int start, int end) { List<TreeNode> list = new ArrayList<>(); if(start > end) { list.add(null); return list; } for(int i = start; i <= end; i++) { for(TreeNode left : generateTrees(start, i - 1)) { for(TreeNode right : generateTrees(i + 1, end)) { TreeNode root = new TreeNode(i); root.left = left; root.right = right; list.add(root); } } } return list; } }
要注意这个终止条件，if(start > end)，这个仅仅当循环中i=start或i=end时才会发生，且start最多比end大于1。
然后是动态规划
class Solution { public List<TreeNode> generateTrees(int n) { if(n == 0) return new ArrayList<>(); List<TreeNode>[] dp = new ArrayList[n + 1]; dp[0] = new ArrayList<>(); dp[0].add(null); for(int i = 1; i <= n; i++) { dp[i] = new ArrayList<>(); for(int j = 0; j < i; j++) { for(TreeNode left : dp[j]) { for(TreeNode right : dp[i - j - 1]) { TreeNode root = new TreeNode(j + 1); root.left = left; root.right = clone(right, j + 1); dp[i].add(root); } } } } return dp[n]; } public TreeNode clone(TreeNode root, int offset) { if(root == null) return root; TreeNode newRoot = new TreeNode(root.val + offset); newRoot.left = clone(root.left, offset); newRoot.right = clone(root.right, offset); return newRoot; } }
LeetCode 95. Unique Binary Search Trees II
原文：https://www.cnblogs.com/rookielet/p/10583967.html