检查树是否是二进制搜索树(BST)

本文介绍了检查树是否是二进制搜索树(BST)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试解决二进制搜索树问题，但是我无法通过所有测试用例.如果树是二进制搜索树，我需要返回true，否则，我需要返回false.谁能告诉我我在做什么错?

I am trying to solve a binary search tree problem, but I can't pass all of the test cases. I need to return true if the tree is a binary search tree, otherwise, I need to return false. Can anyone tell me what I am doing wrong?

''' class node: def __init__(self, data): self.data = data self.left = None self.right = None ''' def checkBST(root): if root.left == None and root.right == None: return True if root == None: return True if root.left != None: if root.left.data < root.data: return True else: return False if root.right != None: if root.right.data > root.data: return True else: return False return chckBST(root.left) and chckBST(root) and chckBST(root.right)

推荐答案

您的代码中有很多多余的if条件.您可以像这样简化它:

You've a lot of redundant if conditions in your code. You can simplify it like so:

def checkBST(root): if root == None or (root.left == None and root.right == None): return True elif root.right == None: return root.left.data < root.data and checkBST(root.left) elif root.left == None: return root.right.data >= root.data and checkBST(root.right) return checkBST(root.left) and checkBST(root.right)

首先，检查所有None条件. python中的短路保证如果第一个条件为False，则第二个条件将不被评估.这使您可以编写简洁的语句，例如return root.left.data < root.data and checkBST(root.left).

First, check for all the None conditions. Short circuiting in python guarantees that if the first condition is False, the second will not be evaluated. This allows you to write succinct statements such as return root.left.data < root.data and checkBST(root.left).

最后，如果左节点和右节点都不是None，请不再次调用checkBST(root).这导致无限递归.

Finally, in the event that neither left nor right nodes are None, do not call checkBST(root) again. This leads to infinite recursion.