题目描述
Given an integer 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.
<pre>
1 3 3 2 1
\ / / / \
3 2 1 1 3 2
/ / \
2 1 2 3
</pre>
解法代码
<pre>
public class Solution {
public List<TreeNode> generateTrees(int n) {
if(n < 1)
return new ArrayList<TreeNode>();
return helper(1, n);
}
public List<TreeNode> helper(int start, int end) {
List<TreeNode> res = new ArrayList();
if(start > end) {
res.add(null);
return res;
}
for(int i = start; i <= end; i ++) {
List<TreeNode> leftChild = helper(start, i - 1);
List<TreeNode> rightChild = helper(i + 1, end);
for(TreeNode left : leftChild) {
for(TreeNode right : rightChild) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
res.add(root);
}
}
}
return res;
}
}
</pre>
思路和想法
对于写递归，有一点很重要，就是要“信任”，信任你的函数能够完成实现的功能（先不管它到底对不对：））。明确这个递归函数输入是什么，输出是什么，有什么作用，然后在写的时候只考虑在这一层要干的事情。拿这个例子讲思路，helper函数是会返回一个包含TreeNode的List，里面包括了这一层可能出现的所有节点值。首先是终止条件。接下来就是主体，我们在每一层都要干什么？比如在某一层还剩1，2，3，4，5共5个节点，因为要求所有的可能性，所以我们应该要每次挑第i个节点，小于i的放到左子树里，大于i的放到右子树里（第一个循环）。接下来就是拼树了，对于在左子树和右子树的集合里分别取一个节点接到我们i节点的左右，在把根节点放到List里就可以了（第二个二层循环）。
然后List是代表这一层可能出现的所有节点值，当函数递归进入后，肯定需要一个新的list来存节点，因此在递归函数的开头需要新建一个ArrayList。
这就是整个写递归的思路。递归一直很困扰我，通过这题算是稍微看到了一点点门道，但是感觉需要提高的地方还是很多。
