Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
這題是NP問題的套路劈愚，for循環(huán)中調(diào)用遞歸挖息。在NQUEENS中有總結(jié)娱局。
我感覺這題思維還挺難的予弧，套用一般的DFS套路還需要想一想，就是樹怎么拼接起來的鸿脓。跟前面一題一樣于购，
我總是會感覺在dfs中先調(diào)用遞歸函數(shù)，后面的東西會執(zhí)行不到篓叶，其實是不對的，可以看之前提的問題羞秤。
public List<TreeNode> generateTrees(int n) {
if(n == 0 ) return new ArrayList<>();
//以root=1開始缸托，root=n結(jié)束
return dfs(1, n);
}
private List<TreeNode> dfs(int left, int right) {
List<TreeNode> res = new ArrayList<>();
if (left > right) {
res.add(null);
return res;
}
for (int i = left; i <= right; i++) {
//左子樹由[left,i-1]的節(jié)點構(gòu)成，右子樹由[i+1,right]的節(jié)點構(gòu)成
List<TreeNode> leftSide = dfs(left, i - 1);
List<TreeNode> rightSide = dfs(i + 1, right);
for (TreeNode lt : leftSide)
for (TreeNode rt : rightSide) {
TreeNode root = new TreeNode(i);
root.left = lt;
root.right = rt;
res.add(root);
}
}
return res;
}
構(gòu)造樹時兩邊要遍歷所有左右的匹配瘾蛋，然后接到根上面俐镐。從兩個for循環(huán)構(gòu)造樹的過程中可以體會到為什么卡特蘭數(shù)是要相乘的。
