尝试验证二叉树是二叉搜索树

Question

我正在学习二叉搜索树，并尝试这个问题二叉树是二叉搜索树还是不是?

通过序遍历我想检查它是否是升序的

def isBst(self,root,prev = None):
if root is not None:

self.isBst(root.left,prev)
if prev != None and root.data <= prev.data:
return False
prev = root
self.isBst(root.right,prev)
else:
return True

在这里，我试图将每个序遍历存储在prev变量中，并检查下一个遍历与prev，如果它小于这意味着它不是BST，否则它将返回True。这就是我想做的。但在这里，我想，但我不明白是什么问题，我在这里做的?它给出None作为输出

有谁能告诉我并帮助我理解这个吗?

Answer 1

一些问题:

• 函数可以返回None，因为if块没有以return语句结束，所以将返回默认的None

• 主要问题是您没有使用递归调用的返回值。假设递归调用返回False，这意味着在某处违反了BST属性…然后，您的代码将忽略该消息，并继续愉快地处理树的其余部分。因此，您至少应该考虑返回值——类似于以下内容(参见下一个要点):

  valid = self.isBst(root.left, prev)
  if not valid:
  return False
  # ... other code...
  return True
  

• 您似乎假设递归调用将修改调用者的prev变量的值，但这是不可能的。当您传递prev作为参数时，您传递的不是变量，而是该变量具有的值，并且递归执行上下文创建自己的prev变量，该变量以提供的值开始。但是，对变量的任何赋值都与调用方的prev变量无关。

与其试图解决这些问题，我建议采用另一种方法，我发现这种方法更直观:在单独的函数中创建一个顺序迭代器:一个只处理的函数，生成一个接一个的值…仅此而已。然后，实际的isBst函数可以迭代该迭代器，并且很容易检测到违规。

如下所示:

class Solution:
def traverse(self, root):
if root:
yield from self.traverse(root.left)
yield root.data
yield from self.traverse(root.right)
def isBst(self, root):
inorder = self.traverse(root)
prev = next(inorder, None)  # smallest
for value in inorder:  # the rest...
if prev > value:
return False
prev = value
return True

使用itertools.tee，您可以使isBst代码更短:

def isBst(self, root):
import itertools
# get two inorder iterators on the tree's values
iprev, icurr = itertools.tee(self.traverse(root))
# advance one of the two
next(icurr, None)
# check the pairs by consuming both iterators in tandem
return all(prev <= curr for prev, curr in zip(iprev, icurr))