在给定值的 BST 查找中，我们可以通过多少种不同的方式查看此特定值？
How many different ways can we see this specific values on a BST lookup of a given value?
The problem statement
When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?
答案：7！/（3！4！）
我不知道他们是怎么得出答案的。
我可以想出以下两点
10
\
20
\
40
\
50
\
70
\
80
\
90
/
60
和
90
/
80
/
70
/
10
\
20
\
30
\
40
\
50
\
60
当我尝试其他事情时，我无法通过访问所有给定值从根节点到包含 60 的节点。
例如
50
/ \
40 90
/ /
20 80
/ /
10 70
/
60
在上面的例子中，我只能按顺序访问50、90、80、70、60，而忽略了10、20、40。那么它声称的答案是如何得出的呢？
可能是我没看懂问题。也许不需要访问所有节点。那样的话怎么想出解决办法呢？
这里有一个小的思想实验：根据提供的信息，BST 的根值是否可能为 20？如果是这样，您将继续移动到右子树以搜索 60（因为 60 > 20），但在这种情况下您永远不会看到值 10，因为 10 必须在左子树中！
同理，树的根可以是80吗？如果是这样，在搜索 60 时，您会在第一步中向左移动 (60 < 80)，但是您永远不会看到 90，因为 90 在左子树中！
这表明我们的树根发生了一些有趣的事情。如果我们在搜索 60 时看到所有这些值，则并非所有这些值都可以是 BST 的根。
那么我们能看到什么是根？一种选择是查看 10。由于集合中的所有剩余值都大于 10，因此不排除任何可能性。另一个选项是 90，因为集合中的所有剩余值都小于 90。
我们现在可以问关于看到根后下降到的子树的根的相同问题。我们必须要么看到剩余值中的最大值，要么看到剩余值中的最小值，否则（使用类似的推理）我们会切断一些我们应该看到的值。
更一般地说，我们看到的每个值都必须是 (1) 大于 60 的最大值或 (2) 小于 60 的最小值。任何其他值都不起作用，并且会截断一些值。
在提供的值中，有四个（10、20、40、50）小于 60，三个（70、80、90）大于 60。当我们搜索 60 时，在每个点，我们需要从第一组中选择最小值或从第二组中选择最大值作为我们在树搜索中看到的下一个值。因此，我们可以想象将 60 搜索为 Ls 和 Rs 的字符串，其中 R 表示 "pick the smallest value from the left group"，L 表示 "pick the largest value from the right group." 例如，RRRRLLL 将为我们提供以下搜索路径：
10
\ R
20
\ R
40
\ R
50
\ R
90
/ L
80
/ L
70
/ L
60
序列 RLRLRLR 会给我们
10
\ R
90
/ L
20
\ R
80
/ L
40
\ R
70
/ L
50
\ R
60
因此，我们的整体问题的答案现在如下：您可以用多少种方法来制作一串 4 个 R 和 3 个 L？答案是 7 选 4（也等于 7 选 3）：我们的字符串中有七个位置，我们可以选择其中四个作为 R，其余为 L，或者选择其中三个作为 L，其余为 L是 R. 那是 7！ /（4！3！），与您看到的答案匹配。
The problem statement
When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?
答案：7！/（3！4！）
我不知道他们是怎么得出答案的。
我可以想出以下两点
10
\
20
\
40
\
50
\
70
\
80
\
90
/
60
和
90
/
80
/
70
/
10
\
20
\
30
\
40
\
50
\
60
当我尝试其他事情时，我无法通过访问所有给定值从根节点到包含 60 的节点。
例如
50
/ \
40 90
/ /
20 80
/ /
10 70
/
60
在上面的例子中，我只能按顺序访问50、90、80、70、60，而忽略了10、20、40。那么它声称的答案是如何得出的呢？
可能是我没看懂问题。也许不需要访问所有节点。那样的话怎么想出解决办法呢？
这里有一个小的思想实验：根据提供的信息，BST 的根值是否可能为 20？如果是这样，您将继续移动到右子树以搜索 60（因为 60 > 20），但在这种情况下您永远不会看到值 10，因为 10 必须在左子树中！
同理，树的根可以是80吗？如果是这样，在搜索 60 时，您会在第一步中向左移动 (60 < 80)，但是您永远不会看到 90，因为 90 在左子树中！
这表明我们的树根发生了一些有趣的事情。如果我们在搜索 60 时看到所有这些值，则并非所有这些值都可以是 BST 的根。
那么我们能看到什么是根？一种选择是查看 10。由于集合中的所有剩余值都大于 10，因此不排除任何可能性。另一个选项是 90，因为集合中的所有剩余值都小于 90。
我们现在可以问关于看到根后下降到的子树的根的相同问题。我们必须要么看到剩余值中的最大值，要么看到剩余值中的最小值，否则（使用类似的推理）我们会切断一些我们应该看到的值。
更一般地说，我们看到的每个值都必须是 (1) 大于 60 的最大值或 (2) 小于 60 的最小值。任何其他值都不起作用，并且会截断一些值。
在提供的值中，有四个（10、20、40、50）小于 60，三个（70、80、90）大于 60。当我们搜索 60 时，在每个点，我们需要从第一组中选择最小值或从第二组中选择最大值作为我们在树搜索中看到的下一个值。因此，我们可以想象将 60 搜索为 Ls 和 Rs 的字符串，其中 R 表示 "pick the smallest value from the left group"，L 表示 "pick the largest value from the right group." 例如，RRRRLLL 将为我们提供以下搜索路径：
10
\ R
20
\ R
40
\ R
50
\ R
90
/ L
80
/ L
70
/ L
60
序列 RLRLRLR 会给我们
10
\ R
90
/ L
20
\ R
80
/ L
40
\ R
70
/ L
50
\ R
60
因此，我们的整体问题的答案现在如下：您可以用多少种方法来制作一串 4 个 R 和 3 个 L？答案是 7 选 4（也等于 7 选 3）：我们的字符串中有七个位置，我们可以选择其中四个作为 R，其余为 L，或者选择其中三个作为 L，其余为 L是 R. 那是 7！ /（4！3！），与您看到的答案匹配。