Блог

Я даю двоичное дерево поиска с n узлами с уникальным значением от 1 до n, и мне нужно вычислить, сколько структурно отличающихся двоичных деревьев поиска я могу сделать из него. Я использую DFS с запоминанием для решения проблемы. По сути, это похоже на то, что если у нас есть n узлов, корневой узел может быть от 1 до n, затем я рекурсивно вычисляю, сколько поддерево может иметь дерево. Кроме того, я запомнил диапазон значений узлов, которые может иметь дерево, и сколько разных деревьев можно создать с этим диапазоном значений узлов, поэтому я не пересчитываю. Я думаю, что время и пространство равны O (n ^ 2), поскольку для моего значения узла дерева может быть n ^ 2 разных диапазона. Кто-нибудь может прокомментировать это?

 class Solution {
    public int numTrees(int n) {
        
        // structrually unique BST with value from 1 to n
        // same structure but different number? no, one way to arrange node
        // from 1 to n start
        // left has num candid - 1 to 1
        // right has num candid   1 to n
        
        Map<Integer, Integer> memo = new HashMap<>();
        
        return numWays(1, n, memo);
    }
    
    
    private int numWays(int low, int high, Map<Integer, Integer> memo) {
        
        if(memo.containsKey(low * 100   high)) {
            return memo.get(low * 100   high);
        }
        
        if(low >= high) return 1;
        int ans = 0;
        for(int i = low; i <= high; i  ) {
            ans = ans   numWays(low, i - 1, memo) * numWays(i   1, high, memo);
        }
        memo.put(low * 100   high, ans);
        return ans;
    }
}

 

Временная сложность в настоящее время равна O (n ^ 3). Верно, что существует только O (n ^ 2) диапазонов и не более O (n ^ 2) пар (low, high), отображаемых в качестве входных данных для функции numWays. Однако функция numWays выполняет O (high-low 1) шагов после запоминания, что является еще одним фактором O (n).

Чтобы ускорить этот процесс, можно заметить, что количество по британскому летнему времени за [1,2,3,4] такое же, как и число по британскому летнему времени за [2,3,4,5] или [3,4,5,6]; только длина массива вопросам (дает вам o(п^2) алгоритм, с небольшим изменением). Другое возможное ускорение происходит от замечая, что за каждое двоичное корневое дерево с n узлами, существует ровно один способ обозначить узлы [1,2,…,N], можно получить по британскому летнему времени, значит, ты ищешь способ/повторение, чтобы рассчитывать корни бинарных деревьев.

Мы также могли бы использовать формулу:

 const f = n => n < 2 ? 1 : (4*n - 2) / (n   1) * f(n - 1);

for (let i=0; i<20; i  )
  console.log(f(i));