【算法】验证二叉搜索树

验证二叉搜索树

描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

解题思路

1.中序遍历数，结果必然是升序。

//用于记录前一个值
    private Integer last;
    //中序遍历树，比较值。时间复杂度:O(n)，空间复杂度:O(n)。
    public boolean isValidBST(TreeNode root) 
    {
        if (root == null) return true;
        
        if (!isValidBST(root.left)) return false;
        
        if (last != null && root.val <= last) return false;
        last = root.val;
        
        if (!isValidBST(root.right)) return false;
        
        return true;
    }

2.遍历树的同时指定上下限范围，每个节点取值范围是上下界，左节点的上界值是父节点，右节点的下界值是父节点。适合所有遍历方式。

//层序遍历树，上下界比较值。时间复杂度:O(n)，空间复杂度:O(n)。
    public boolean isValidBST3(TreeNode root) 
    {
        if (root == null) return true;
                
        Queue<TreeNode> nodes = new LinkedList<>();
        Queue<Integer> mins = new LinkedList<>();
        Queue<Integer> maxs = new LinkedList<>();
        
        nodes.offer(root);
        mins.offer(null);
        maxs.offer(null);
        
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.poll();
            Integer min = mins.poll();
            Integer max = maxs.poll();
            
            if (min != null && node.val <= min) return false;
            if (max != null && node.val >= max) return false;
            
            if (node.left != null) {
                nodes.offer(node.left);
                mins.offer(min);
                maxs.offer(node.val);
            }
            
            if (node.right != null) {
                nodes.offer(node.right);
                mins.offer(node.val);
                maxs.offer(max);
            }
        }
        
        return true;
    }

Objective-C版：

OC版的解法