python实现leetcode之98. 验证二叉搜索树

解题思路

定义一个辅助函数
返回：是不是合法的二叉搜索树，最大值，最小值
然后递归调用
根树的返回值第一个元素就是答案

98. 验证二叉搜索树

代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return vmm(root)[0]


def vmm(tree):
    """
    返回值：是不是合法的二叉搜索树，最大值，最小值
    """
    if not tree:
        return True, None, None
    else:
        lv, lmx, lmi = vmm(tree.left)
        rv, rmx, rmi = vmm(tree.right)
        if not lv or not rv:
            return False, None, None
        elif lmx and lmx >= tree.val:
            return False, None, None
        elif rmi and rmi <= tree.val:
            return False, None, None
        else:
            return True, rmx or tree.val, lmi or tree.val