这个前面的问题问有多少种方法有插入值1 - 7成二叉搜索树，会导致下面的树：

This earlier question asked how many ways there were to insert the values 1 - 7 into a binary search tree that would result in the following tree:

       4
     /   \
    2     6
   / \   / \
  1   3 5   7

（答案是80，的方式）。

(The answer is 80, by the way).

假设更普遍，你给出一个任意BST拿着一些设定值，并想知道有多少可能的方法有，将这些值转换，将最终产生结果树一个BST。是否有一个有效的算法来确定呢？

Suppose more generally that you're given an arbitrary BST holding some set of values and want to know how many possible ways there are to insert those values into a BST that would end up producing the resulting tree. Is there an efficient algorithm for determining this?

谢谢！

推荐答案

我们可以用一个巧妙的递归算法解决这个问题。

We can solve this using a clever recursive algorithm.

由于我们的基本情况，如果您将得到一个空的树，还有就是建立一个树只有一个办法 - 不要将任何值

As our base case, if you are given an empty tree, there is exactly one way to build that tree - don't insert any values.

有关递归情况下，让我们假设你有一个BST看起来是这样的：

For the recursive case, let's suppose that you have a BST that looks like this:

              v
             / \
            L   R

下面，v是根，且L和R是正确的子树，分别

Here, v is the root, and L and R are the right subtrees, respectively.

如果我们要建立这个二叉搜索树，我们就必须先插入V到开始 - 如果我们没有，V不会是根。当我们插入V，我们需要插入的元素进行排序，这将导致子树L和R重建。这里最棘手的部分是，我们并不需要建立R或反之亦然之前建立所有的L;我们可以插入来自L某些元素，然后一些从研发要素，然后由L以上的元素，从研发则更多的元素，等等。

If we want to build up this binary search tree, we would have to start off by inserting v first - if we didn't, v wouldn't be the root. After we insert v, we need to insert the elements in an ordering that will cause the subtrees L and R to be rebuilt. The tricky part here is that we don't need to build up all of L before building up R or vice-versa; we could insert some elements from L, then some elements from R, then more elements from L, then more elements from R, etc.

幸运的是，有一个有用的观察，我们可以做到的。假设使得S 大号是一个序列的元素，如果插入的BST，形成BST L.同样，设S 研究是元素的序列，如果插入一个BST形成BST R.如果我们考虑的序列S1 →和S 研究的任何可能的交织，我们将结束与元素，如果插入序列只包含V A BST，将建立树

Fortunately, though, there is a useful observation we can make. Suppose that SL is a sequence of elements that, if inserted into a BST, forms the BST L. Similarly, let SR be a sequence of elements that if inserted into a BST form the BST R. If we consider any possible interleaving of the sequences SL and SR, we will end up with a sequence of elements that, if inserted into a BST containing just v, will build up the tree

   v
  / \
 L   R

作为一个例子，考虑这个树：

As an example, consider this tree:

       4
     /   \
    2     6
   / \   / \
  1   3 5   7

一种可能的序列，其构建左子树​​（保持1，2，3）2，1，3，一个可能的序列，其构建右子树是6,5，这些序列7.如任何可能的交织，在插入时到只包含根节点4 BST，最终将打造出上述BST。例如，任何这些序列将工作：

One possible sequence that builds the left subtree (holding 1, 2, 3) is 2, 1, 3. One possible sequence that builds the right subtree is 6, 5, 7. Any possible interleaving of those sequences, when inserted into a BST containing just the root node 4, will end up building out the above BST. For example, any of these sequences will work:

 2, 1, 3, 6, 5, 7
 2, 6, 1, 5, 3, 7
 6, 5, 2, 1, 3, 7
 ...

由于给出任何序列S1 →和S 研究的建立L和R就可以交错按任意顺序，我们可以写出一个很好的公式数量序列，将打造出一棵树的v为根，L为左子树，和R作为它的右子树：

Since given any sequences SL and SR that build up L and R we can interleave them in any order, we can write out a nice formula for the number of sequences that will build out a tree with v as its root, L as its left subtree, and R as its right subtree:

＃方式=（＃交错小号→和S 研究的）时间; （＃可能的小号→ S）次; （＃可能的小号研究 S）

# ways = (# interleaves of SL and SR) × (# possible SLs) × (# possible SRs)

如果你仔细想想，在该产品的最后两项，可以通过递归发现为左，右子树工作插入序列号发现。这意味着，如果我们能弄清楚有多少可能的交错有两个序列，那么我们就可以判断有多少可能的插入序列将通过递归评估上述EX pression建立一个给定的树！

If you think about it, the last two terms in this product can be found by recursively finding the number of insertion sequences that work for the left and right subtrees. This means that if we can figure out how many possible interleavings there are for the two sequences, then we can determine how many possible insertion sequences will build up a given tree by evaluating the above expression recursively!

那么有多少的交错有哪些？如果我们给定长度为m的两个序列和n与他们没有重复，那么我们可以拿出与以下观察这些序列的交错的数量。考虑序列

So how many interleavings are there? If we're given two sequences of length m and n with no duplicates in them, then we can come up with the number of interleavings of those sequences with the following observation. Consider the sequence

L L L ... L R R R ... R
  m times     n times

此序列将回馈一系列Ls和Rs其中LS的数目等于长度为m和Rs的数目的序列中的元素数量的任何置换等于所述序列中的元素数的长度为n。我们可以跨preT这个序列描述如何建立交错的方式 - 我们看到L所有的时间，我们插入从左边序列的元素，我们看到的R任何时候，我们插入一个元素从正确的顺序。例如，考虑了序列4,1，0,3和2，7。然后置换LLRLRL给出序列

Any permutation of this sequence will give back a series of Ls and Rs where the number of Ls is equal to the number of elements in the sequence of length m and the number of Rs is equal to the number of elements in the sequence of length n. We can interpret this sequence as a way of describing how to build up the interleaving - any time we see L, we insert an element from the left sequence, and any time we see an R, we insert an element from the right sequence. For example, consider the sequences 4, 1, 0, 3 and 2, 7. Then the permutation LLRLRL gives the sequence

 4, 1, 2, 0, 3, 7
 L  L  R  L  R  L

如果我们为m L的和n的r的序列开始，不同排列的数量回来为

If we start off with a sequence of m L's and n R's, the number of distinct permutations comes back as

(m + n)!
-------- = (m + n) choose m
 m!  n!

此举行，因为有（M + N）！重新排序的LS和RS，如果他们所有不同的可能途径。由于他们都没有，每一个排序数米！ N！太多的时间，因为我们可以将重排L的不加区别地将R的不可区分。另一种方式考虑，这是考虑到该组中的交织索引的{1，2，3，...，M + N}，则选择其中米来填充与来自第一序列元素，隐填充其余其中与从右侧的序列元件。

This holds because there are (m + n)! possible ways of reordering the Ls and the Rs if they were all distinct. Since they aren't, every ordering is counted m! n! too many times because we can permute the L's indistinguishably and the R's indistinguishably. Another way to think about this is to consider the set {1, 2, 3, ..., m + n} of indices in the interleaving, then to choose m of them to fill with elements from the first sequence, implicitly filling the rest of them with elements from the right sequence.

好......我们现在已经确定的交织的长度m和n的两个序列的路的数目的一种方式。因此，我们有以下几点：

Okay... we now have a way of determining the number of ways of interleaving two sequences of length m and n. Therefore, we have the following:

＃方式=（＃交错小号→和S 研究的）时间; （＃可能的小号→ S）次; （＃可能的小号研究 S）

# ways = (# interleaves of SL and SR) × (# possible SLs) × (# possible SRs)

=（（M + N）选择N）次; （＃可能的小号→ S）次; （＃可能的小号研究 S）

= ((m + n) choose n) × (# possible SLs) × (# possible SRs)

其中M是元素的左子树的数，n是在右子树的元素数。耶！

Where m is the number of elements in the left subtree and n is the number of elements in the right subtree. Yay!

因此​​，我们可以写出来的伪code这个算法：

We can therefore write out pseudocode for this algorithm:

function countInsertionOrderings(Tree t) {
    if t is null, return 1;
    otherwise:
       let m = numElementsIn(t.left);
       let n = numElementsIn(t.right);
       return choose(m + n, n) * 
              countInsertionOrderings(t.left) *
              countInsertionOrderings(t.right);
}

此算法总共为O（n）次乘法执行，其中n是树中节点的数量，以及访问每一个节点恰好一次（假设被缓存在每个节点中的BST元素的数量）。这确实的没有的意思是算法的时间为O（N），但是，因为要乘这些数字相加所需的工作将快速增长的数字越来越大。

This algorithm performs a total of O(n) multiplications, where n is the number of nodes in the tree, and visits every node exactly once (assuming the number of elements in the BST are cached at each node). This does not mean the algorithm runs in time O(n), though, because the work required to multiply these numbers together will grow rapidly as the numbers get larger and larger.

希望这有助于！