讨论/《初级算法》 - 验证二叉搜索树/
《初级算法》 - 验证二叉搜索树
共 29 个回复

1,递归写法

做这题之前我们首先要明白什么是二叉搜索树,就是每个节点左子树的值都比当前节点小,右子树的值都比当前节点大。所以看到这里我们最先想到的就是递归,我最先想到的是下面这种写法(注意是错误的

public boolean isValidBST(TreeNode root) {
    if (root == null)
        return true;
    if (root.left != null && root.val <= root.left.val || root.right != null && root.val >= root.right.val)
        return false;
    return isValidBST(root.left) && isValidBST(root.right);
}

如果一个结点是空的,我们默认他是有效的二叉搜索树。

否则如果左节点不为空,我们要判断是否大于左节点的值。

如果右节点不为空,我们还要判断小于右节点的值。

然后我们再以左右两个子节点用相同的方式判断。看起来好像没什么问题,但我们好像忽略了一个每个节点的上限和下限,比如下面这棵树
image.png
注意6这个节点不光要小于15而且还要大于10,所以这里的每一个节点都是有一个范围的,上面的代码我只判断了6比15小,但没有和10进行比较,所以代码是错误的。这里我们来给每个节点添加一个范围,如果不在这个范围之内直接返回false,比如6的范围是(10,15),很明显他不在这个范围内,所以他不是二叉搜索树。根节点的范围我们从Long.MIN_VALUE到Long.MAX_VALUE,来看下代码

public boolean isValidBST(TreeNode root) {
    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
    if (root == null)
        return true;
    //每个节点如果超过这个范围,直接返回false
    if (root.val >= maxVal || root.val <= minVal)
        return false;
    //这里再分别以左右两个子节点分别判断,
    //左子树范围的最小值是minVal,最大值是当前节点的值,也就是root的值,因为左子树的值要比当前节点小
    //右子数范围的最大值是maxVal,最小值是当前节点的值,也就是root的值,因为右子树的值要比当前节点大
    return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
}

看下运行结果
image.png


2,中序遍历递归

根据二叉搜索树的性质我们知道,中序遍历二叉搜索树,遍历的结果一定是有序的,如果不明白中序遍历的可以看下前面的373,数据结构-6,树。中序遍历时,判断当前节点是否大于中序遍历的前一个节点,也就是判断是否有序,如果不大于直接返回 false。

//前一个结点,全局的
TreeNode prev;

public boolean isValidBST(TreeNode root) {
    if (root == null)
        return true;
    //访问左子树
    if (!isValidBST(root.left))
        return false;
    //访问当前节点:如果当前节点小于等于中序遍历的前一个节点直接返回false。
    if (prev != null && prev.val >= root.val)
        return false;
    prev = root;
    //访问右子树
    if (!isValidBST(root.right))
        return false;
    return true;
}

看下运行结果
image.png


3,中序遍历非递归

如果对树的中序遍历比较熟悉的话,或者看过之前写的《373,数据结构-6,树》,这里面也有树的中序遍历的递归和非递归两种写法。我们完全可以把上面中序遍历的递归改为非递归。

public boolean isValidBST(TreeNode root) {
    if (root == null)
        return true;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode pre = null;
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (pre != null && root.val <= pre.val)
            return false;
        //保存前一个访问的结点
        pre = root;
        root = root.right;
    }
    return true;
}

看下运行结果
image.png


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

16

区间递归

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    // (min,max)
    public boolean isValidBST(TreeNode p,long min,long max)
    {
        if(p == null)
            return true;
        if(p.val <= min || p.val >= max)
            return false;
        return isValidBST(p.left,min,p.val) && isValidBST(p.right,p.val,max);
    }
}
9

中序遍历即可

class Solution {
public:
    vector<int> vals;
    bool isValidBST(TreeNode* root) {
        InOrder(root);
        for(int i = 0; i < vals.size() - 1; i++){
            if(vals[i] >= vals[i + 1])
                return false;
        }
        return true;
    }
private:
    void InOrder(TreeNode* root){
        if(root != nullptr){
            InOrder(root->left);
            vals.push_back(root->val);
            InOrder(root->right);
        }
    }
};
3

解法1无法覆盖root.val=Integer.MAX_VALUE的case

1

二叉搜索树的中序遍历结果必然是递增数组或递减数组,因此中序遍历从头到尾判断是否满足递增或递减条件即可。

class Solution {
    List<Integer> list = new ArrayList<>();

    public boolean isValidBST(TreeNode root) {
        inOrderTraversal(root);
        for(int idx=1;idx<list.size();idx++){
            if(list.get(idx-1)>=list.get(idx)){
                return false;
            }
        }
        return true;
    }

    private void inOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left);
        list.add(root.val);
        inOrderTraversal(root.right);
    }
}

分析一下:
实际上判断是否满足递增数组或递减数组时只需要前一个节点的值,因此可只保留前节点值即可。
中序遍历(参考大佬们的解法)

//前节点
    TreeNode preNode;
    //先序遍历
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        //左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        //中间节点
        if (preNode != null && root.val <= preNode.val) {
            return false;
        }
        preNode = root;
        //右子树
        if (!isValidBST(root.right)) {
            return false;
        }
        return true;
    }

大佬们的最佳解答,给定范围的先序遍历:

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return false;
        }
        //判断左右子树是否满足范围
        return isValidBST(root.left, null, root.val) && isValidBST(root.right, root.val, null);
    }

    //先序遍历,当前节点不满足范围直接返回,否者判断左右子树是否满足搜索二叉树条件
    private boolean isValidBST(TreeNode node, Integer start, Integer end) {
        if (node == null) {
            return true;
        }
        //判断本节点
        if (start != null && node.val <= start) {
            return false;
        }
        if (end != null && node.val >= end) {
            return false;
        }
        //判断左右节点
        return isValidBST(node.left, start, node.val) && isValidBST(node.right, node.val, end);
    }
1

python3 DFS深度递归

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # node > node.left and node < node.right
        # 使用DFS 深度递归解法
        def dfs(node, min_val, max_val):
            if not node:
                return True

            # 判断 根值 与 上下区间值比较
            if not min_val < node.val < max_val:
                return False
            
            # 递归深度判断 
            return dfs(node.left, min_val, node.val) and dfs(node.right, node.val, max_val)
        return dfs(root, -2**32, 2**32) # 判断上下区间
1

因为3这个右子树的叶子节点比 根节点的5还要小.. 不满足

[5,4,6,null,null,3,7] 不是二叉搜索树吗?为什么答案是 false
image.png

image.png

/**
 * 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 root) {
        return ((root.left==null || isValidBSTRange(root.left, root, null)) && (root.right==null || isValidBSTRange(root.right, null,root)));
    }
    public boolean isValidBSTRange(TreeNode root, TreeNode max, TreeNode min) {
        if ((max!=null&&root.val>=max.val)||(min!=null&&root.val<=min.val)) {
            return false;
        }
        return ((root.left==null || isValidBSTRange(root.left, (max==null||max.val>root.val)?root:max, min)) 
        && (root.right==null || isValidBSTRange(root.right, max, (min==null||min.val<root.val)?root:min)));
    }
}
/**
 * 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 root) {
        List<Integer> list = new ArrayList<>();
        dfs(root,list);
        for (int i = 0; i < list.size()-1; i++) {
            if (list.get(i + 1) <=list.get(i)) {
                return false;
            }
        }
        return true;
    }
    public void dfs(TreeNode node,List<Integer> list) {
        //边界
        if (node == null) {
            return ;
        }
        dfs(node.left, list);
        list.add(node.val);
        dfs(node.right, list);
    }
}

image.png