Different BST II
出处
给出n,生成所有由1...n为节点组成的不同的二叉查找树
样例
给出n = 3,生成所有5种不同形态的二叉查找树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Solution
使用递归来做。
- 先定义递归的参数为左边界、右边界,即1到n.
- 考虑从left, 到right 这n个数字中选取一个作为根,余下的使用递归来构造左右子树。
- 当无解时,应该返回一个null树,这样构造树的时候,我们会比较方便,不会出现左边解为空,或是右边解为空的情况。
- 如果说左子树有n种组合,右子树有m种组合,那最终的组合数就是n*m. 把这所有的组合组装起来即可
Complexity
这个不是很确定
时间复杂度 O(n2 ) 空间复杂度 O(n)
Code
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @paramn n: An integer
* @return: A list of root
*/
public List<TreeNode> generateTrees(int n) {
return dfs(1, n);
}
public List<TreeNode> dfs(int left, int right) {
List<TreeNode> ret = new ArrayList<TreeNode>();
// The base case;
if (left > right) {
ret.add(null);
return ret;
}
for (int i = left; i <= right; i++) {
List<TreeNode> lTree = dfs(left, i - 1);
List<TreeNode> rTree = dfs(i + 1, right);
for (TreeNode nodeL: lTree) {
for (TreeNode nodeR: rTree) {
TreeNode root = new TreeNode(i);
root.left = nodeL;
root.right = nodeR;
ret.add(root);
}
}
}
return ret;
}
}