题目描述
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
链接：https://leetcode-cn.com/problems/validate-binary-search-tree/
理解
定义
二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：
- 若左子树不为空，则 左子树上所有结点的值均小于它的根结点的值
- 若右子树不为空，则 右子树上所有结点的值均大于它的根结点的值
- 它的左右子树也分别为二叉搜索树
结论
根据以上“二叉搜索树”的定义我们会得到以下结论：
如果采用“中序遍历”的方式遍历一棵“二叉搜索树”，得到的会是一个“升序”序列。
思路
从“结论”得出的结果出发(中序遍历后得到的数据序列是一个升序序列)，“中序遍历给定的二叉树，当遍历每个节点的时候，判断当前节点的值是否 小于等于 其前驱节点的值”
- 如果当前节点的值“小于等于”其前驱节点的值，则证明此二叉树不是一个 二叉搜索树。
- 否则，继续遍历当前节点的左右子树上的剩余节点。
根据“二叉搜索树”的定义，二叉搜索树上节点的取值存在一个“范围”，这个范围存在一个“上限”和“下限”。
如何确定一个节点的取值范围呢？？？
实现
按照思路1中的分析，中序遍历此二叉树，把每个节点与其前驱节点的值进行比较
/**
* 记录当前节点的前驱节点
* 每次调用“isValidBSTByInOrder()”前需要把此变量进行重置
*/
private static TreeNode2 bsfByInOrderPreNode = null;
/**
* 采用中序遍历,判断访问的"当前结点"的值是否"小于等于"前驱结点的值
*/
public static boolean isValidBSTByInOrder(TreeNode2 node) {
if (node == null) {
return true;
}
//左子树
if (!isValidBSTByInOrder(node.left)) {
return false;
}
//判断当前结点是否"小于等于"前驱结点的值
if (bsfByInOrderPreNode != null
&& node.val <= bsfByInOrderPreNode.val) {
return false;
}
//缓存前驱结点
bsfByInOrderPreNode = node;
//右子树
return isValidBSTByInOrder(node.right);
}
