数据结构与算法——Java实现 52.力扣98题——验证二叉搜索树
我将一直向前，带着你给我的淤青
—— 24.11.3
98. 验证二叉搜索树
给你一个二叉树的根节点
root，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3] 输出：true示例 2：
输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。
方法1 递归求解
思路
提前设置一个prev对象，首先设置为最小值，从根节点开始，对每个节点进行递归，左—值—右中序遍历，不断更新节点值与prev存储的上一个节点的值，直到找到了不符合二叉树的定义的子树，返回false，若将二叉树全部遍历完成，则判断符合二叉搜索树的规则，返回true
/*** 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;* }* }*/
class Solution {long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode node){if (node == null){return true;}// 中序遍历：左 - 根 - 右boolean a = isValidBST(node.left);if(prev >= node.val){return false;}else{prev = node.val;}boolean b = isValidBST(node.right);return a && b;}
}
方法2 中序遍历+双指针+栈
思路
将所有的子节点全部压入栈中，当遍历到最左边的节点时，开始弹栈，在弹栈的过程中，不断比较弹出值与右边节点的大小，由于二叉树的特性：左子树 < 根结点 < 右子树以及栈的特性：先进先出FIFO，每弹出一个节点时，进行比较，如果发现有不符合二叉树规则的节点，则返回false
算法全流程:
① 初始化:
`TreeNode p = node；`：设置当前节点 'p' 为根节点。
’LinkedList<TreeNode> stack = new LinkedList<>()；‘：创建一个栈用于存储节点。
'long prev = Long.MIN_VALUE；'：初始化 `prev` 为' Long.MIN_VALUE
② 中序遍历:
使用栈来模拟递归调用，首先将所有左子节点压入栈中。
当到达最左边的叶子节点时，开始弹栈并处理节点值。
每次弹出一个节点时，检查其值是否大于'prev'，如果不大于，则更新 'prev` 为当前节点的值，并将 'p` 指向当前节点的右子节点，继续遍历。如果大于，则判断为不合法，返回 ‘False’
③ 结束条件
如果遍历完所有节点且没有发现违反BST性质的情况，返回 ‘True'
注：为保证确定最小值，使用Long类型的最小值MIN_VALUE
/*** 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;* }* }*/
class Solution {public boolean isValidBST(TreeNode node) {TreeNode p = node;LinkedList<TreeNode> stack = new LinkedList<>();long prev = Long.MIN_VALUE; // 代表上一个值while (p != null || !stack.isEmpty()) {if (p != null) {// push 压栈stack.push(p);p = p.left;} else {// pop 弹栈TreeNode pop = stack.pop();// 处理值if (prev >= pop.val){return false;}prev = pop.val;p = pop.right;}}return true;}
}
方法3 判断合法 — 上下界
思路
对于每一个节点来说，其左边的祖先节点key值都要比原节点小，其右边的节点key值都要比原节点大，如果对于每个节点都符合要求，则返回true，否则返回false
/*** 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;* }* }*/
class Solution {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);}
}