Пространственная сложность генерации всех возможных бинарных деревьев поиска - PullRequest
Новая
       65

Пространственная сложность генерации всех возможных бинарных деревьев поиска

0 голосов
/ 03 мая 2020

Я использовал следующий алгоритм рекурсии, чтобы вычислить возможные случаи бинарных деревьев поиска, учитывая его число узлов, равное 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 (lG_l) элементов, где l обозначает уровень, а G_l обозначает количество возможных деревьев с l узлами.

Тогда мне кажется, что пространственная сложность рекурсии должна быть nG_n + ... + 1G_1.

...