题目
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
分析
这道题不细心的话容易踩坑，一般惯性思维都会只比较当前节点与左右子节点的值，一开始我认为这是一道简单题，快速做完后发现是错的。
那上面的方法错在哪里呢? 其实它忽略了一种情况：左子节点的右节点可能会比当前节点大，这种情况满足了当前节点与左右子点比较的条件，但这样的树还是不能满足搜索树的条件，搜索树要求左子树所有节点都小于当前节点。
但如果拿子树所有节点依次跟当前节点比较，会有大量重复比较，效率低。
最好的判断方法是拿当前与左子树最大节点及右子树最小节点比较，怎么样拿到左子树最大节点及右子树最小节点呢?
以拿左子树最大节点为例，它的最大节点一定是树的最右节点。
代码
/**
* 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 {
TreeNode pre;
public boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
if(!isValidBST(root.left)){
return false;
}
if(pre != null && pre.val >= root.val){
return false;
}
pre = root;
return isValidBST(root.right);
}
}结果
?
?
关注个人微信公众号：肌肉码农，回复“好友”讨论问题。
?