二叉搜索树--验证二叉搜索树

验证二叉搜索树-力扣 98 题

解题思路：利用二叉树中序遍历的特性：遍历出来的结果是升序的即符合二叉搜索树

对于二叉树中序遍历不是太理解的，作者推荐的小白书：二叉树的初步认识_加瓦不加班的博客-CSDN博客

中序非递归实现

// 解法1. 中序遍历非递归实现 1ms
public boolean isValidBST(TreeNode root) {TreeNode p = root;LinkedList<TreeNode> stack = new LinkedList<>();long prev = Long.MIN_VALUE;//记录上一个值while (p != null || !stack.isEmpty()) {if (p != null) {stack.push(p);p = p.left;} else {TreeNode pop = stack.pop();//如果相邻两个节点相等，也不应当通过测试if (prev >= pop.val) {return false;}prev = pop.val;p = pop.right;}}return true;
}

记录 prev 需要用 long，否则若测试用例中最小的节点为 Integer.MIN_VALUE 则测试会失败

注意，如果相邻两个节点相等，也不应当通过测试，例如，下面的树也是不合法的

中序递归实现

方法一：

// 解法2. 中序遍历递归实现(全局变量记录 prev) 0ms
long prev = Long.MIN_VALUE;
public boolean isValidBST2(TreeNode node) {if (node == null) {return true;}boolean a = isValidBST2(node.left);//加上这个是为了 当发现不符合时就不再去遍历剩下的节点 如果不加if (!a) 条件，就还好继续判断剩下节点是否合法就有点多此一举if (!a) {return false;}if (prev >= node.val) {return false;}prev = node.val;return isValidBST2(node.right);
}

方法二：

// 解法3. 中序遍历递归实现(局部变量记录 prev) 0ms
public boolean isValidBST(TreeNode root) {if (root == null) {return true;}return doValid(new AtomicLong(Long.MIN_VALUE),root);
}public boolean doValid(AtomicLong prev, TreeNode node) {if (node == null) {return true;}//左子树是否合法boolean a = doValid(prev, node.left);//值的判断if (prev.get() >= node.val) {return false;}prev.set(node.val);//右子树是否合法boolean b = doValid(prev, node.right);//最终两边都合法才算合法return a && b;
}

为何不能用 Long 或 long？因为它们都是局部变量且不可变，因此每次赋值时，并不会改变其它方法调用时的 prev

要么把 prev 设置为 AtomicLong，要么把 prev 设置为全局变量，而不要采用方法参数这样的局部变量

上述代码并不是最有效率的，分析过程见视频讲解

上下限递归

解题思路：

/*
能否只判断父亲比左孩子大，比右孩子小? 答：不行的，案例2中：4的右边有个3就不符合，
也就是说这个思路只考虑了父与子之间的大小关系，而没有考虑到祖先与子孙之间的大小关系
案例1： 4
/ \
2 6
/ \
1 3
*/
/*案例2：
4
/ \
2 6
/ \
3 7
*/
// 解法4. 上下限递归实现 0ms
// -∞ 4 +∞
// / \
// -∞ 2 4 6 +∞
// / \
// 4 3 6 7 +∞
//什么叫上下限递归实现？比如上面的4，4是根节点，所以4的上限：+∞ 下限：-∞
//2的上限：4 下限：-∞
//6的上限：+∞ 下限：4
//3的上限：6 下限：4
//7的上限：+∞ 下限：6

  /*能否只判断父亲比左孩子大，比右孩子小? 答：不行的，案例2中：4的右边有个3就不符合，也就是说 这个思路只考虑了父与子之间的大小关系，而没有考虑到祖先与子孙之间的大小关系案例1：               4/   \2     6/ \1   3*//*案例2：4 /   \2     6 / \3   7 */// 解法4. 上下限递归实现 0ms
//			    -∞ 4 +∞
//               /   \
//           -∞ 2  4  6 +∞
//                   / \
//                4 3 6 7 +∞
//什么叫上下限递归实现？  比如上面的4，4是根节点，所以4的上限：+∞  下限：-∞
//2的上限：4   下限：-∞    
//6的上限：+∞  下限：4   
//3的上限：6  下限：4 
//7的上限：+∞  下限：6
public boolean isValidBST(TreeNode node) {return doValid(node, Long.MIN_VALUE, Long.MAX_VALUE);
}private boolean doValid(TreeNode node, long min, long max) {if (node == null) {return true;}if (node.val <= min || node.val >= max) {return false;}return doValid(node.left, min, node.val) && doValid(node.right, node.val, max);
}

设每个节点必须在一个范围内：(min, max)，不包含边界，若节点值超过这个范围，则返回 false

对于 node.left 范围肯定是 (min, node.val)

对于 node.right 范围肯定是 (node.val, max)

一开始不知道 min，max 则取 java 中长整数的最小、最大值

本质是前序遍历 + 剪枝