98 验证二叉搜索树
01
题目信息
题目地址： https://leetcode-cn.com/problems/validate-binary-search-tree/
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
02
解法一：递归
和上题一样可以很好的想到递归的思路，左边都是越来越小，右边是越来越大。这个地方容易产生一种错觉。
1
错误思路及代码：
就是只比较左右子节点的与父节点大小关系，如上图第一次是满足的，接下来递归左节点但他没有子节点结束并返回true,递归右节点也满足关系，继续递归其右节点因无子节点结束，左边同理。整个递归完成最终是true,但因为3比根节点5小应该在左子树不满足二叉搜索树
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
if(root.left != null && root.left.val >= root.val)
return false;
if(root.right != null && root.right.val <= root.val)
return false;
return isValidBST(root.left) && isValidBST(root.right);
}
那么问题就在于我们要比较的东西是什么？
对于叶子节点2来说它比3小就可以没有限制，对于叶子节点6的位置它只能大于3并且小于5才有效 也就是说我们往左边走即是小那么就有一个上限之后不能超过，往右边走即是大就有一个下限。
3
按照整个过程如上图，从根节点开始往左进入递归，往左了以后这边的值都小于上限5并且3满足小于5继续递归找到2也是满足并且2之后的树上限是3，继续递归为空了出去，执行下一步的兄弟节点判断时超过了上线结束
代码如下：
public boolean isValidBST(TreeNode root) {
return process(root, null, null);
}
//递归方法
public boolean process(TreeNode node, Integer min, Integer max) {
if (node == null) return true;
if (min != null && node.val <= min) return false;
if (max != null && node.val >= max) return false;
if (!process(node.right, node.val, max)) return false;
if (!process(node.left, min, node.val)) return false;
return true;
}
4
03
解法二：中序遍历
中序遍历是树的一种遍历方式，先数左子树在数中间在数右子树，那么通过中序遍历如果是真的二叉搜索树是一个从小到大的序列
上图中序遍历：[2,3,6,5,3,6,7]
//记录前一个
Integer pre = null;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
// 访问左子树
if (!isValidBST(root.left)) return false;
// 访问当前节点：如果当前节点小于等于中序遍历的前一个节点.即不满足
if (pre != null && root.val <= pre) return false;
pre = root.val;
// 访问右子树
return isValidBST(root.right);
}
6
04
总结
其实两种解法也都是属于深度优先，一个在过程中处理遍历方式为后序，一个是中序。使用不同的遍历过程那么就需要想清楚在这种遍历下处理判断逻辑。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-12-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录