在二叉搜索树中查找有效序列

Question

假设1到1000的整数已经排列在二叉搜索树中，现在要找到数字363。下列哪个序列不可能是遍历节点的顺序？

a) 2, 252, 401, 398, 330, 344, 397, 363 ;

b) 924, 220, 911, 244, 898, 258, 362, 363 ;

c) 925, 202, 911, 240, 912, 245, 363 ;

d) 2, 399, 387, 219, 266, 382, 381, 278, 363 ;

e) 935, 278, 347, 621, 299, 392, 358, 363.

是否有必要制作模式？请写出最小形式的属性进行检查。

谢谢。

- XPRO

---

我投票关闭此问题，因为它不是一个编程问题。 - Scott Hunter

这是一个非常有趣的问题，涉及的内容更多是算法而不是编程。 - Dave

Scott Hunter，这是关于算法的问题，我需要一个答案。 - XPRO

Answer 1

范围[min，max] - 初始化为[1,1000]

键 - 要搜索的目标密钥

seq [1，N] - 二叉搜索树中的数字序列

思路是跟踪有效范围[min，max]。最初，所有数字从1到1000都在范围内。如果您遇到一个带有键2的节点，而您的目标是363，则会向右转。当您向右转时，您将遇到此子树中的任何关键字应该大于2。因此，您更新范围中的min为2。现在您的范围是[3,1000]。当您遇到252时，范围变为[253,1000]。在401处，您向左转，因此此子树中的所有键都必须小于401。因此，将max设置为400，它变为[253,400]。

现在，在序列中的任何一点，您都需要检查值是否在范围内。如果不是，则存在违规行为。如果密钥匹配，则必须是序列中的最后一个数字。

这是伪代码

boolean validate(seq[1,N],key,range)
    for i from 1 to N
        if(seq[i] < range.min || seq[i] > range.max)
            return false
        if(key < seq[i])
            range.max := key-1
        else if(key > seq[i])
            range.min := key+1
        else
            return i=N
    return true

- arunmoezhi

---

我认为所提出的算法中有一个错别字。 应该是 range.max := seq[i]-1 而不是 range.max := key-1 - 和最小值的想法一样。 - immutableT

Answer 2

在这里进行操作：https://www.cs.usfca.edu/~galles/visualization/BST.html，一个接一个地将每个数字放在左上角的“insert”旁边，然后点击“insert”。当您输入数字时，它会构建一棵二叉树。

对于每个序列都要这样做，并比较它们的外观。

这是“a)”的路径：

这是一条单一的链。以下是尝试通过“c)”的路线：

这是一个从上到下不止一条路径的图表，其中有一些错误的分支。如果树中有363并且您直接前往它，就不会走错路了。

在c）中，911在240处向左分叉，在912处向右分叉。

在e）中，347在621处向右分叉，在299处向左分叉。

它们不能是到达363的遍历序列，因为每个列表中的一个节点不在通往363的路上。

[截图来自https://www.cs.usfca.edu/~galles/visualization/BST.html]

- TessellatingHeckler

---

请您能否详细解释一下？ - XPRO

完成！非常感谢。 - XPRO

Answer 3

直觉：

如果 sequence[i] > sequence[i+1]，则路径已在左子树中搜索，序列中的下一个元素必须小于等于sequence[i]

否则，路径包括右子树的元素，序列中的下一个元素必须大于等于sequence[i]

我们可以使用上述逻辑编写暴力解决方案，其时间复杂度为O(n^2)

# checks if any elements in the sequence is greater than val
def any_element_greater(sequence, val):
  for e in sequence:
    if e > val:
      return True
  return False

# checks if any elements in the sequence is lesser than val
def any_element_lesser(sequence, val):
  for e in sequence:
    if e < val:
      return True
  return False

# checks if the sequence is valid
def is_valid_seq(sequence):
  if len(sequence) < 2:
    return True
  
  prev = sequence[0]
  for idx, val in enumerate(sequence):
    if prev > val:
            # checks if the rest of the sequence is valid based on direction
      if any_element_greater(sequence[idx:], prev):
        return False
    elif prev < val:
            # checks if the rest of the sequence is valid based on direction
      if any_element_lesser(sequence[idx:], prev): 
        return False
    prev = val

  return True

优化：

我们可以使用max和min变量来传递有效范围 - 记忆化。

def valid_sequence(sequence, i=0, m_min=1, m_max=1000):
  '''
  Checks if the Sequence is a correct path in BST
  Parameters:
    sequence: path to the data in the BST
    i: current data we are validating in the path
    m_min: data should be more than m_min
    m_max: data should be less than m_max
  Returns:
    Boolean: If the sequence is a valid path in BST
  '''
    if len(sequence) == 0:
        return True

  data = sequence[i]

  # check if data is in valid range
  if not (m_min <= data <= m_max):
    return False

  # Base case, return if we reached the end
  if i == len(sequence) - 1:
    return True

  '''
  Adjust min, max for the next data elements
  depends on the next element in the sequence
  '''
  next = sequence[i+1]
  if next > data:
    m_min = max(m_min, data)
  else:
    m_max = min(m_max, data)

  return valid_sequence(sequence, i+1, m_min, m_max)

测试：

options = {
    'a': [2, 252, 401, 398, 330, 344, 397, 363],
    'b': [924, 220, 911, 244, 898, 258, 362, 363],
    'c': [925, 202, 911, 240, 912, 245, 363],
    'd': [2, 399, 387, 219, 266, 382, 381, 278, 363],
    'e': [935, 278, 347, 621, 299, 292, 358, 363]
}

for option in options:
  print(f'{valid_sequence(options[option])} \t - {option}. {options[option]}')

结果：

True     - a. [2, 252, 401, 398, 330, 344, 397, 363]
True     - b. [924, 220, 911, 244, 898, 258, 362, 363]
False    - c. [925, 202, 911, 240, 912, 245, 363]
True     - d. [2, 399, 387, 219, 266, 382, 381, 278, 363]
False    - e. [935, 278, 347, 621, 299, 292, 358, 363]

推理：

在选项c中，当我们进入240的左子树时，912大于911，因此它是无效的。

在选项e中，我们从347向右走，但在序列中遇到299和292，因此它是无效的。

- Sahith Vibudhi