[LeetCode]98.检验二叉搜索树的有效性

题目

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

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

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/validate-binary-search-tree

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

由题，中序遍历是严格的递增，则是BST。

不需要将中序遍历结果存储，只需在中序遍历过程中比较序列临近两元素即可。

代码

public static boolean isValidBST(TreeNode root) {
Stack stack = new Stack<>();
TreeNode curNode = root;
long maxVal = Long.MIN_VALUE;
while (curNode != null || !stack.isEmpty()) {//
while (curNode != null) {
stack.push(curNode);
curNode = curNode.left;
}
curNode = stack.pop();
if (curNode.val > maxVal) {
maxVal = curNode.val;
curNode = curNode.right;//
} else {
return false;
}
}
return true;
}