AlgoPressAppearance
0098-验证二叉搜索树
https://leetcode.cn/problems/validate-binary-search-tree
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
示例 2： 
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
树中节点数目范围在[1, 10^4] 内
-2^31 <= Node.val <= 2^31 - 1
思路
根据二叉搜索树的特征，递归检测 左侧所有的节点都必须小于根节点的值 右侧所有的节点都必须大于根节点的值 左子树和右子树都符合二叉搜索树的特征
- 如果只考虑上面一个节点的边界，即 node.left < node.val && node.right > node.val 会缺失掉对根节点的判断
- 从根节点一路
比如下面的节点，其中最后 3 是不符合二叉树的特征的，但是他在子树 6,3,7 里面是符合的。 虽然他从是大于根节点2的，但是从节点5开始，因为他是排在右边的，所以必须大于5. 因此，每个节点是否合法，他都有个下边界和上边界 对于左子树，他的上边界就是 node.val , 下边界就是之前的min 于右子树，他的下边界就是 node.val，上边界就是之前的max 边界不停的递归传入下一层
2
/ \
0 5
/\
4 6
/\
3 7
参考代码
csharp
public class Solution {
private bool isValidBST(TreeNode root, long min, long max){
if(root == null){
return true;
}
if(root.val <= min || root.val >= max){
return false;
}
return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}
public bool IsValidBST(TreeNode root) {
if(root == null){
return true;
}
return isValidBST(root, long.MinValue, long.MaxValue);
}
}
思路2：中序遍历
中序遍历的方式是 “左子树” -> 根 -> 右子树， 因此整个遍历结果必须是按升序排列的。 所以遍历之后，再判断整个输出数组，当出现 nums[i+1] < nums[i] 的时候说明结果是不合法的。 我们再多考虑一层，实际上在中序遍历的过程当中，我们只要判断目前值和前面的值，是否是升序的就可以知道整个结果是否合法。 中间我们用一个变量记录 pre 的值，在第一个数值进行判断的时候，我们设置 pre = long.MinValue;(考虑到 node.val 最小的数值是 int.MinValue)
参考代码
csharp
public class Solution {
private long pre = long.MinValue;
private bool dfs(TreeNode root){
if(root == null){
return true;
}
bool result = dfs(root.left);
if(root.val <= pre || !result){
return false;
}
pre = root.val;
return result && dfs(root.right);
}
public bool IsValidBST(TreeNode root) {
if(root == null){
return true;
}
return dfs(root);
}
}