98.验证二叉搜索树题目来源：https://leetcode-cn.com/problems/validate-binary-search-tree题目给定一棵二叉树，判断其是否为有效的二叉搜索树。假设一棵二叉搜索树具有以下特点：节点的左子树只包含小于当前节点的数字。节点的右子树仅包含大于当前节点的数字。所有的左子树和右子树本身必须是二叉搜索树。示例1：输入：2/\13输出：true示例2：输入：5/\14/\36输出：false解释：输入为：[5,1,4,null,null,3,6].根节点的值为5，但其右子节点的值为4。解题思路：中序遍历根据题意，二叉搜索树有如下性质：当二叉树的左子树不为空时，左子树上所有节点的值都较少比其根节点的值。当子树不为空时，右子树上所有节点的值都大于根节点的值。左右子树也是二叉搜索树。从上面的性质我们可以看出，二叉搜索树[间序遍历]得到的值一定是升序排列的。所以有了这个特性，我们可以考虑在中序遍历的时候检查当前节点的值是否大于上一次中序遍历中遍历的节点的值。如果都大于那个，说明这个序列是升序排列的，符合前面关于性质的结论，那么整棵树就是一棵二叉查找树。关于【中序遍历】，是一种二叉树遍历。在二叉树中，中序遍历先遍历左子树，然后访问根节点，最后遍历右子树。具体实现代码如下。代码实现#定义一个二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defisValidBST(self,root:TreeNode)->bool:stack=[]#-inf表示负无穷inorder=float('-inf')whilerootorstack:#将左边的点压入栈中whileroot:stack.append(root)root=root.left#进行中序遍历root=stack.pop()#如果当前结点的值小于上一次中序遍历的值，则不是二叉搜索树whileroot.val<=inorder:returnFalse#更新中序遍历值inorder=root.valroot=root.rightreturnTrue实现结果以上就是解决问题的主要内容《98. 验证二叉搜索树》基于基于栈实现中序遍历的思路关于二叉搜索树的性质。欢迎关注微信公众号《书所集录》
