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(nodenull){returntrue;}return(leftnode.valnode.valright)check(node.left,left,node.val)check(node.right,node.val,right);}}方法2中序遍历 中序遍历时可以把二叉搜索树看成一个有序数组。比较相邻元素的大小即可。classSolution{longpreLong.MIN_VALUE;publicbooleanisValidBST(TreeNoderoot){//中序遍历if(rootnull){returntrue;}//遍历左子树if(!isValidBST(root.left)){returnfalse;}intcurroot.val;//当前节点与前一个节点的值比较if(curpre){returnfalse;}//更新需要比较的值precur;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(nodenull){returnnewlong[]{Long.MAX_VALUE,Long.MIN_VALUE};}long[]leftTreecheck(node.left);long[]rightTreecheck(node.right);intxnode.val;if(xleftTree[1]||xrightTree[0]){//如果是比较左子树的话当前节点永远小于leftTree[1]//如果是比较右子树的话当前节点永远大于rightTree[0]//这样就能识别这是一个非二叉搜索树returnnewlong[]{Long.MIN_VALUE,Long.MAX_VALUE};}returnnewlong[]{Math.min(leftTree[0],x),Math.max(rightTree[1],x)};}}
