98.验证二叉搜索树
1、概要
中序遍历下，输出的二叉搜索树节点的数值是有序序列。
验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。 注意二叉搜索树中不能有重复元素
这道题目比较容易陷入两个陷阱：
- 不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。（要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。）
- 避免 初始化最小值，取到最左面节点的数值来比较。当前的要大于左边节点
2、思路
递归
- 确定递归函数，返回值以及参数
//避免初始化最小值，记录前一个节点，取最左边节点的数值来比较
TreeNode* pre = NULL;
bool isValidBST(TreeNode* root)
- 确定终止条件
//二叉搜索树也可以为空
if(root == null) return true;
- 确定单层递归的逻辑
bool left = isValidBST(root.left);
if(pre!=null && pre.val >= root.val) return false;
pre = root;⭐⭐⭐
bool right = isValidBST(root.right);
return left && right;
迭代
中序统一迭代模版稍微修改
添加pre记录节点：TreeNode pre = null;
else内 加入核心逻辑，当前的要大于前一个！
3、代码
class Solution {
TreeNode pre;
public boolean isValidBST(TreeNode root) {
return resCurSion(root);
//return iteRation(root);
}
public boolean iteRation(TreeNode root){
if(root == null){return false;}
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
if(cur!=null){
if(cur.right !=null){
stack.push(cur.right);
}
stack.push(cur);
stack.push(null);
if(cur.left!=null){
stack.push(cur.left);
}
}else{
cur = stack.pop();
if(pre !=null && cur.val<=pre.val){⭐⭐⭐
return false;
}
pre = cur;⭐⭐⭐
}
}
return true;
}
public boolean resCurSion(TreeNode root){
if (root == null) {
return true;
}
// 左
boolean left = resCurSion(root.left);
// 中 ⭐⭐⭐
if (pre != null && root.val <= pre.val) {
return false;
}
pre = root;
// 右
boolean right = resCurSion(root.right);
return left && right;
}
}