网站建立服务seo关键词使用

题目重述

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

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

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

示例 1:

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

示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 乍一看二叉搜索树特点验证起来细节需要考虑的挺多，其实二叉搜索树这样的特点，中序遍历完一定是一个升序队列
• 那么我们可以去对该树进行二叉树的中序遍历，在遍历的过程中，若出现不满足升序的情况，则返回false，即不是二叉搜索树

Java实现

class Solution {public boolean isValidBST(TreeNode root) {long preNum = Long.MIN_VALUE;if(root == null){return true;}Stack<TreeNode> stack = new Stack<>();while(root != null || !stack.empty()){while (root!=null){stack.push(root);root = root.left;}root = stack.pop();// 如果不满足升序，那么不是二叉搜索树if(root.val <=preNum){return false;}// 更新前驱，至于为什么是在这里，可以与二叉树的中序遍历思路类比// 中序遍历的时候是需要在这里add到结果数组的，那么在这里我们可以把握到顺序preNum = root.val;root = root.right;}return true;}
}