98. 验证二叉搜索树
给你一个二叉树的根节点root，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
- 节点的左子树只包含严格小于当前节点的数。
- 节点的右子树只包含严格大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
方法一：前序遍历 1、需要判断当前节点所在的区间，是否当前节点大于其左子树所在区间的右端点，是否小于其右子树所在区间的左端点。 2、根节点处于（负无穷，正无穷）区间中，其左子树处于（负无穷，根节点值）区间中，其右子树处于（根节点值，正无穷）区间中。 3、每访问一个节点，则需要更新其左子树和右子树所在的区间值。/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicbooleanisValidBST(TreeNoderoot){returncheck(root,Long.MIN_VALUE,Long.MAX_VALUE);}publicbooleancheck(TreeNodenode,longleft,longright){//前序遍历if(node==null){returntrue;}return(left<node.val&&node.val<right)&&check(node.left,left,node.val)&&check(node.right,node.val,right);}}方法2：中序遍历 中序遍历时，可以把二叉搜索树看成一个有序数组。比较相邻元素的大小即可。classSolution{longpre=Long.MIN_VALUE;publicbooleanisValidBST(TreeNoderoot){//中序遍历if(root==null){returntrue;}//遍历左子树if(!isValidBST(root.left)){returnfalse;}intcur=root.val;//当前节点与前一个节点的值比较if(cur<=pre){returnfalse;}//更新需要比较的值pre=cur;returnisValidBST(root.right);}}方法3：后序遍历 1、拿到当前节点左子树的最小值和最大值，以及当前节点的右子树的最小值和最大值 2、满足二叉搜索树：当前节点的值大于左子树的最大值，以及小于右子树的最小值 3、不满足时：返回负无穷和正无穷。这样非二叉搜索树永远返回负无穷和正无穷。 4、如果是空节点，则返回正无穷和负无穷。这样无论如何，都能满足条件，不会因为空节点而判断是非二叉搜索树。classSolution{publicbooleanisValidBST(TreeNoderoot){//后序遍历// return check(root)[1] != Long.MAX_VALUE;returncheck(root)[0]!=Long.MIN_VALUE;}publiclong[]check(TreeNodenode){//后序遍历if(node==null){returnnewlong[]{Long.MAX_VALUE,Long.MIN_VALUE};}long[]leftTree=check(node.left);long[]rightTree=check(node.right);intx=node.val;if(x<=leftTree[1]||x>=rightTree[0]){//如果是比较左子树的话，当前节点永远小于leftTree[1]//如果是比较右子树的话，当前节点永远大于rightTree[0]//这样就能识别这是一个非二叉搜索树returnnewlong[]{Long.MIN_VALUE,Long.MAX_VALUE};}returnnewlong[]{Math.min(leftTree[0],x),Math.max(rightTree[1],x)};}}
