Общая функция, генерирующая BST в некотором диапазоне значений - PullRequest
Новая
       18

Общая функция, генерирующая BST в некотором диапазоне значений

0 голосов
/ 07 апреля 2019

Этот вопрос относится к https://leetcode.com/problems/unique-binary-search-trees-ii

Я пытаюсь реализовать универсальную функцию, которая генерирует все структурно эквивалентные BST с заданным диапазоном последовательных целочисленных значений [m...n], где n>=m. Идея состоит в том, что если размер этого диапазона (т. Е. n-m+1) одинаков, то независимо от выбора n и m число структурно эквивалентных деревьев должно быть одинаковым. Например, у нас могут быть (n,m) = (1,9) и (n,m) = (5,13), где размер обоих равен 9. Эти 2 диапазона будут генерировать одинаковые BST с точки зрения структуры, за исключением того, что значения различны. В этом случае мы поменялись бы 1 на 5, 2 на 6, .... и 9 на 13, или наоборот. Другими словами, после генерации всех структурно эквивалентных BST для (n,m) = (1,9) я хочу иметь возможность использовать это, чтобы легко поменять значения в [1 ... 9] для [5 ... 13] без необходимости регенерации BSTs.

Итак, я хочу спроектировать некоторую функцию, которая генерирует структурно эквивалентные деревья для некоторого ввода n-m+1, сохранит эти структурно эквивалентные BST, а затем сможет подключить любой n,m и даст мне все структурно эквивалентные с узловыми значениями в диапазоне [n ... m]. Я не хочу регенерировать BST для будущих входов того же размера диапазона.

Проблема Leetcode определяет узел BST как 

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };

Возможно ли это с помощью определения этого TreeNode? Значение, которое оно хранит, имеет тип int. Если бы он был типа int *, то я мог бы придумать, как это сделать, но текущее определение кажется проблематичным.

1 Ответ

0 голосов
/ 07 апреля 2019

Решение этой проблемы имеет временную сложность O(n*Cn), где Cn - каталонское число.Независимо от того, как вы создаете (или копируете, или перемещаете) деревья для подзадач, вы не можете добиться большей сложности, потому что вам нужно напечатать (сравнить и т. Д.) Все деревья в конце.

Выесть следующие опции:

  1. Создайте копию каждого дерева в соответствии с предложением Hiroki answer.Вы закончите в то же время сложности, и вы удвоите свою память.

  2. Изменить значения дерева на лету .Вы можете создать функцию-оболочку вокруг дерева val, например 

    int getValue(TreeNode* node, int shift){
     return node->val + shift;
}

, и использовать эту функцию, например, если вы хотите напечатать все деревья.Временная сложность одинакова, и вы не выделяете дополнительную память для сдвинутых деревьев.Однако в случае Leetcode это невозможно, так как платформа сравнивает результаты с использованием val, и вы не можете изменить его на использование getValue.

Измените определение дерева и используйте int* val.Изменить структуру на платформе Leetcode невозможно, но давайте рассмотрим и этот случай.Если у вас есть все деревья, сгенерированные для некоторого диапазона [1,n], вы можете преобразовать все эти деревья в другой диапазон только в O(n).Это мило.Но если вы посмотрите глубже, вы поймете, что вам нужно каким-то образом использовать эти деревья (например, чтобы распечатать его, пройти его и т. Д.).Итак, вы только что виртуально трансформировали эти деревья, но в итоге вы снова получите ту же временную сложность O(n*Cn).Так что, даже если бы это было возможно, это было бы бесполезно.

В заключение: Для платформы Leetcode у вас есть только опция 1. В общем случае у вас есть два других варианта, но ни один из этих 3 вариантов не поможет вам уменьшить сложность времени.

...