时间戳

首页 > 解决方案 > 在某些值范围内生成 BST 的通用函数

c++ - 在某些值范围内生成 BST 的通用函数

问题描述

这个问题与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。这两个范围在结构方面会生成相同的 BST，只是值不同。在这种情况下，我们将 1 替换为 5，将 2 替换为 6，......，以及 9 替换为 13，反之亦然。换句话说，在为(n,m) = (1,9)，我希望能够使用它轻松地将 [1...9] 中的值交换为 [5...13] 而无需重新生成 BST。

所以我想设计一些函数，为一些输入生成结构上等价的树n-m+1，存储这些结构上等价的 BST，然后可以插入任何n,m东西，让它给我所有结构上等价的节点值在 [n. ..米]。我不想为将来相同范围大小的输入重新生成 BST。

Leetcode 问题将 BST 节点定义为

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

这是否可能与如何TreeNode定义？它存储的值是 type int。如果它是 type int *，那么我可以想办法做到这一点，但目前的定义似乎有问题。

标签： c++data-structuresbinary-search-tree

解决方案

这个问题的解决方案具有时间复杂度O(n*Cn)，其中Cn是加泰罗尼亚数。无论您如何为子问题创建（或复制或移动）树，都无法获得更好的复杂性，因为您最终需要打印（比较等）所有树。

您有以下选择：

  1. 按照Hiroki回答的建议创建每棵树的副本。您将以相同的时间复杂度结束，并且您的记忆力将加倍。

  2. 即时修改树值。您可以在树周围创建一个包装函数，val例如

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

并在您想打印所有树时使用此功能。时间复杂度是相同的，并且您不会为移位的树分配额外的内存。但是，在 Leetcode 的情况下，这是不可能的，因为平台比较结果是使用的val，你不能将其更改为使用getValue.

  1. 更改树的定义并使用int* val. 在 Leetcode 平台上是不可能改变结构的，但让我们也考虑一下这种情况。如果您为某个范围生成了所有树，[1,n]则可以将所有这些树转换为不同的范围O(n)。那很好。但是如果你看得更深，你会意识到你需要以某种方式使用这些树（例如打印它、遍历它等等）。因此，您只是虚拟地转换了这些树，但最终您将再次以相同的时间复杂度结束O(n*Cn)。因此，即使有可能，它也不会有用。

总结：对于 Leetcode 平台，您只有一个选项1.通常情况下您还有其他两个选项，但这三个选项都不能帮助您降低时间复杂度。

推荐阅读