判断一棵树是否为二叉搜索树（二叉排序树） python

　　输入一棵树，判断这棵树是否为二叉搜索树。首先要知道什么是排序二叉树，二叉排序树是这样定义的，二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

　　（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

　　（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

　　（3）左、右子树也分别为二叉排序树；

　　（4）没有键值相等的节点

　　#方法1，直接判断

　　直接判断的关键在于不能只是单纯地判断根、左、右三个节点的大小关系，左子树的右节点不仅要大于父节点，还要小于父节点的父节点，右子树的左节点不仅要小于父节点，还要大于父节点的父节点。判断代码如下。

class TreeNode:

    def __init__(self, x):

        self.val = x

        self.left = None

        self.right = None

class Solution:

    def isValidBST(self, root):

        """

        :type root: TreeNode

        :rtype: bool

        """

        if not root:

            return True

        def isBSTHelper(node, lower_limit, upper_limit):

            #节点值应大于下限，小于上限

            if lower_limit is not None and node.val <= lower_limit:

                return False

            if upper_limit is not None and upper_limit <= node.val:

                return False

            #随着向下遍历，对于左子树，被不断更新的是上限值（必须小于其父节点），对于右子树，被不断更新的是下限值（必须大于其父节点）

            left = isBSTHelper(node.left, lower_limit, node.val) if node.left else True

            if left:

                right = isBSTHelper(node.right, node.val, upper_limit) if node.right else True

                return right

            else:

                return False

        return isBSTHelper(root, None, None)

　　#2 利用中序遍历

　　根据二叉排序树的特点，按照中序遍历的顺序，应当符合当前遍历到的节点值大于前一个遍历到的节点值，即中序遍历序列是一个有序序列，可以直接对中序遍历得到的序列进行判断，也可以在遍历的过程中进行判断。第二种方法的判断代码如下

 def isbst(self,node):

        global lastvalue

        lastvalue=float('-inf')    #遍历的前一个节点的值

        def isbst2(node):

            global lastvalue

            if node==None:

                return True

            if isbst2(node.left) is not True:

                return False

            if node.val<lastvalue:

                return False

            lastvalue=node.val#更新

            if isbst2(node.right) is not True:

                return False

            return True

        return isbst2(node)

巴特西

判断一棵树是否为二叉搜索树（二叉排序树） python

最新文章

热门文章