面试题 04.05. 合法二叉搜索树

实现一个函数，检查一棵二叉树是否为二叉搜索树。

示例 1:
输入:

输出: true

示例 2:
输入:

输出: false
解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 ，但是其右子节点值为 4 。

Python 解答：
1.中序遍历

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

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        flag = True
        node = None
        def isHelper(root):
            if not root:
                return 
            else:
                isHelper(root.left)
                nonlocal node, flag
                if node:
                    if root.val <= node.val:
                        flag = False
                node = root
                isHelper(root.right)
        isHelper(root)
        return flag  

2.递归

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

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:

        def isHelper(root, low, high):
            if not root:
                return True
            else:
                curleft = root.val > low
                curright = root.val < high
                if curleft and curright:
                    return isHelper(root.right, root.val, high) and isHelper(root.left, low, root.val)
                else: return False

        return isHelper(root, float('-inf'), float('inf'))

3.中序遍历非递归

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

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        stack = []
        pre = None
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            if stack:
                root = stack.pop()
                if pre and root.val <= pre.val:
                    return False
                pre = root
                root = root.right

        return True