擅长:python、mysql、java
<p>另一种方法是只按顺序遍历BST,然后检查它是否已排序。按顺序对BST的遍历进行排序</p>
<pre><code>def inorder(node):
if node is None:
return
yield from inorder(node.left)
yield node.data
yield from inorder(node.right)
inorder_traversal = list(inorder(root))
print(all(i<=j for i, j in zip(inorder_traversal, inorder_traversal[1:]))) # check if sorted
</code></pre>
<p>由于<code>all</code>的短路特性,您可以引入<code>itertools.tee</code>以获得更好的性能</p>
<pre><code>inorder_traversal = inorder(root)
a, b = tee(inorder_traversal) # copy the `inorder_traversal` iterator
next(b) # discard first element
print(all(i<=j for i, j in zip(a,b))) # check if sorted
</code></pre>
<p>有关<code>tee</code>如何工作的更多信息,请参考此答案<a href="https://stackoverflow.com/questions/5434891/iterate-a-list-as-pair-current-next-in-python">Iterate a list as pair (current, next) in Python</a></p>