英文:
Space Complexity of generating all possible binary search trees
问题
我使用了以下递归算法来计算给定节点数为n的二叉搜索树可能的情况。
public List<TreeNode> generateTrees(int n) {
if(n == 0){
List<TreeNode> empty = new ArrayList<TreeNode>();
return empty;
}
return recurHelper(1, n);
}
public List<TreeNode> recurHelper(int start, int end){
if(start > end){
TreeNode nan = null;
List<TreeNode> empty = new ArrayList<TreeNode>();
empty.add(nan);
return empty;
}
List<TreeNode> result = new ArrayList<TreeNode>();
for(int i = start; i <= end; i++){
List<TreeNode> left = recurHelper(start, i-1);
List<TreeNode> right = recurHelper(i+1, end);
for(TreeNode leftBranch:left){
for(TreeNode rightBranch:right){
TreeNode tree = new TreeNode(i);
tree.left = leftBranch;
tree.right = rightBranch;
result.add(tree);
}
}
}
return result;
}
我想知道递归的空间复杂度是多少，是否应该是O(h)，其中h是树的高度？
我认为不应该是O(h)，因为在每个级别上，我们都在存储一个由O(lG_l)个元素组成的结果，其中l表示级别，G_l表示具有l个节点的可能树的数量。
然后，在我看来，递归的空间复杂度应该是nG_n + ... + 1G_1。
英文:
I used the following recursion algorithm to calculate the possible cases of binary search trees given its number of nodes being n
public List<TreeNode> generateTrees(int n) {
if(n == 0){
List<TreeNode> empty = new ArrayList<TreeNode>();
return empty;
}
return recurHelper(1, n);
}
public List<TreeNode> recurHelper(int start, int end){
if(start > end){
TreeNode nan = null;
List<TreeNode> empty = new ArrayList<TreeNode>();
empty.add(nan);
return empty;
}
List<TreeNode> result = new ArrayList<TreeNode>();
for(int i = start; i <= end; i++){
List<TreeNode> left = recurHelper(start, i-1);
List<TreeNode> right = recurHelper(i+1, end);
for(TreeNode leftBranch:left){
for(TreeNode rightBranch:right){
TreeNode tree = new TreeNode(i);
tree.left = leftBranch;
tree.right = rightBranch;
result.add(tree);
}
}
}
return result;
}
I wonder what is the space complexity for the recursion, should it be O(h), where h is the height of the tree?
I do not think so because at each level we are storing a result consisting of O(lG_l) elements, where l stands for the level and G_l stands for the number of possible trees with l nodes.
Then it seems to me that the space complexity of the recursion should be nG_n + ... + 1G_1.
专注分享java语言的经验与见解，让所有开发者获益！
评论