题目
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左
子树
只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3]
输出:true
解1
class Solution {
TreeNode pre;
public boolean isValidBST(TreeNode root) {
boolean[] result = { true };
dfs(root, result);
return result[0];
}
public void dfs(TreeNode root, boolean[] result) {
if (root == null) {
return;
}
dfs(root.left, result);
if (pre != null && pre.val >= root.val) {
result[0] = false;
}
pre = root;
dfs(root.right, result);
}
}
解2
class Solution {
public boolean isValidBST(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
TreeNode pre = null;
while(!stack.isEmpty() || cur != null){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if(pre != null && pre.val >= cur.val){
return false;
}
pre = cur;
cur = cur.right;
}
return true;
}
}```