题目：
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.1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
confused what "{1,#,2,3}" means?
链接：
题解：
题目提示用dp，但真用dp的话内存会不够。所以这次我们使用递归。一开始也没什么头绪，discussion里面有些大神写得很好。方法是 - 从1至n遍历数字时，每次把所有数字分为三部分， 当前数字，比当前数字小的部分，以及比当前数字大的部分， 使用新的list分别存储这两部分。从左部和右部分别按顺序取值，和当前i一起组合起来，成为当前i的一个解，当左右两部分遍历完毕以后，就得到了当前i的所有解。接着计算下一个i的解集。
Time Complexity - O(2n)， Space Complexity - O(2n)
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public List generateTrees(int n) { return generateTrees(1, n); } private List generateTrees(int lo, int hi) { List res = new ArrayList<>(); if(lo > hi) { res.add(null); return res; } for(int i = lo; i <= hi; i++) { List left = generateTrees(lo, i - 1); List right = generateTrees(i + 1, hi); for(TreeNode l : left) { for(TreeNode r : right) { TreeNode root = new TreeNode(i); root.left = l; root.right = r; res.add(root); } } } return res; }}
递归构造得很巧妙，要多加练习。
二刷:
跟一刷的方法一样，还是类似于mergesort的divide and conquer，先计算左右两边，然后用i创建root节点，接下来assign左子树和右子树并且把结果保存到res里。 200题以后也有一道和这个很类似，好像是burst balloon之类的。
Java:
Time Complexity - O(2n)， Space Complexity - O(2n)
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public List generateTrees(int n) { if (n <= 0) { return new ArrayList (); } return generateTrees(1, n); } private List generateTrees(int lo, int hi) { List res = new ArrayList<>(); if(lo > hi) { res.add(null); return res; } for(int i = lo; i <= hi; i++) { List left = generateTrees(lo, i - 1); List right = generateTrees(i + 1, hi); for(TreeNode l : left) { for(TreeNode r : right) { TreeNode root = new TreeNode(i); root.left = l; root.right = r; res.add(root); } } } return res; }}
三刷:
方法和二刷一样。要注意理解思路，如何构造辅助方法来进行递归。
Java:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public List generateTrees(int n) { if (n <= 0) return new ArrayList (); return generateTrees(1, n); } private List generateTrees(int lo, int hi) { List res = new ArrayList(); if (lo > hi) { res.add(null); return res; } for (int i = lo; i <= hi; i++) { List left = generateTrees(lo, i - 1); List right = generateTrees(i + 1, hi); for (TreeNode l : left) { for (TreeNode r : right) { TreeNode root = new TreeNode(i); root.left = l; root.right = r; res.add(root); } } } return res; }}
Update: 每天进步一点点
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public List generateTrees(int n) { if (n <= 0) return new ArrayList (); return generateTrees(1, n); } private List generateTrees(int lo, int hi) { List res = new ArrayList<>(); if (lo > hi) res.add(null); for (int i = lo; i <= hi; i++) { List leftList = generateTrees(lo, i - 1); List rightList = generateTrees(i + 1, hi); for (TreeNode left : leftList) { for (TreeNode right : rightList) { TreeNode root = new TreeNode(i); root.left = left; root.right = right; res.add(root); } } } return res; }}
Reference：
https://leetcode.com/discuss/22628/recursive-java-solution-make-binary-search-characteristic
https://leetcode.com/discuss/33003/java-recursive-solution-straight-forward
https://leetcode.com/discuss/10254/a-simple-recursive-solution
https://leetcode.com/discuss/3440/help-simplify-my-code-the-second-one <- Python
https://leetcode.com/discuss/9790/java-solution-with-dp
https://leetcode.com/discuss/81728/java-2ms-solution-beats-92%25