題目描述

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>

思路和想法

對于寫遞歸，有一點(diǎn)很重要，就是要“信任”，信任你的函數(shù)能夠完成實(shí)現(xiàn)的功能（先不管它到底對不對：））。明確這個遞歸函數(shù)輸入是什么，輸出是什么，有什么作用，然后在寫的時候只考慮在這一層要干的事情。拿這個例子講思路，helper函數(shù)是會返回一個包含TreeNode的List，里面包括了這一層可能出現(xiàn)的所有節(jié)點(diǎn)值。首先是終止條件。接下來就是主體，我們在每一層都要干什么？比如在某一層還剩1，2，3，4，5共5個節(jié)點(diǎn)，因?yàn)橐笏械目赡苄裕晕覀儜?yīng)該要每次挑第i個節(jié)點(diǎn)，小于i的放到左子樹里，大于i的放到右子樹里（第一個循環(huán)）。接下來就是拼樹了，對于在左子樹和右子樹的集合里分別取一個節(jié)點(diǎn)接到我們i節(jié)點(diǎn)的左右，在把根節(jié)點(diǎn)放到List里就可以了（第二個二層循環(huán)）。
然后List是代表這一層可能出現(xiàn)的所有節(jié)點(diǎn)值，當(dāng)函數(shù)遞歸進(jìn)入后，肯定需要一個新的list來存節(jié)點(diǎn)，因此在遞歸函數(shù)的開頭需要新建一個ArrayList。
這就是整個寫遞歸的思路。遞歸一直很困擾我，通過這題算是稍微看到了一點(diǎn)點(diǎn)門道，但是感覺需要提高的地方還是很多。