98. 验证二叉搜索树

题目来源：https://leetcode-cn.com/problems/validate-binary-search-tree

题目

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

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

解题思路

思路：中序遍历

根据题意，二叉搜索树有如下的性质：

• 当二叉树的左子树不是空时，左子树上的所有节点值都小于它根节点的值
• 当二叉树的右子树不为空时，右子树上所有节点值都大于根节点的值
• 左右子树同样也是二叉搜索树

从上面的性质可以看出，二叉搜索树【中序遍历】得到的值一定是升序的。那么就这个特性，我们在中序遍历的时候就可以考虑检查当前节点的值是否大于前一个中序遍历到的节点的值。如果都大于则说明这个序列是升序的，那么就与前面就性质所得出的结论是吻合的，那么整棵树就是二叉搜索树。

关于【中序遍历】，它是二叉树遍历的一种。在二叉树中，中序遍历首先遍历左子树，然后访问根节点，最后遍历右子树。

具体实现代码如下。

代码实现

# 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 = []
        # -inf 表负无穷
        inorder = float('-inf')

        while root or stack:
            # 将左点压入栈中
            while root:
                stack.append(root)
                root = root.left
            
            # 进行中序遍历
            root = stack.pop()
            # 如果当前节点的值小于前面中序遍历的值时，就不是二叉搜索树
            while root.val <= inorder:
                return False
            # 更新中序遍历的值
            inorder = root.val
            root = root.right
        
        return True

实现结果

以上就是根据二叉搜索树的性质，用栈实现中序遍历的思路，进而解决《98. 验证二叉搜索树》问题的主要内容。

欢迎关注微信公众号《书所集录》