Количество бинарных поисковых деревьев

Question

Каково количество бинарных деревьев поиска с 20 узлами с элементами 1,2,3, ..., 20, для которых корень дерева равен 12, а корень левого поддерева - 7? а) 2634240 б) 1243561 в) 350016 г) 2642640

Объяснение вместе с ответом было бы полезно.

Я применил формулу каталонского числа, но результат не подходит для опций, так что это просто для уверенности.

Answer 1

• По сути, вам нужно рассчитать количество уникальных BST, возможных для определенного количества узлов.

• В итоге конечным результатом будет умножение этих чисел.

• Если это было на экзамене, то вам придется сделать умножение. В противном случае вы можете решить эту проблему программно, используя dynamic programming.

КОД:

class Solution {
        public int numTrees(int n) {
           if(n < 3) return n;
           int[] dp = new int[n+1];
           dp[0] = 1; // just initializing it as base case
           dp[1] = 1;// meaning, only 1 possibility for 1 node.
           dp[2] = 2;// meaning, only 2 possibilities for 2 nodes.

           for(int i=3;i<=n;++i){
               for(int j=1;j<=i;++j){
                   int nodes_on_left_of_j  = j - 1;
                   int nodes_on_right_of_j = i - j;
                   dp[i] += dp[nodes_on_left_of_j] * dp[nodes_on_right_of_j]; // so multiply left side possibilites with right side possibilites for a particular root node.
               }
           }

           return dp[n];
        }
    }

Answer 2

Используя каталонские числа , считая полные двоичные деревья с n узлами, ответ будет d) 2642640 = 14 * 132 * 1430. Это возможности расширения (под) деревьев от каждого из наших неизвестные поддеревья.

           12
          /  \
         7    (8 nodes)
        / \
(6 nodes) (4 nodes)

Обновление :

Как предложил Марк Дикинсон в комментариях ниже, чтобы уточнить: «узлы», упомянутые на диаграмме выше и в первом утверждении, являются «внутренними» узлами, которые мы организуем всеми способами, тогда как n th Каталонское число насчитывает полных двоичных деревьев с n+1 листовыми узлами . Двоичные деревья с l листовыми узлами имеют l - 1 внутренние узлы .