1. 首页
  2. Leetcode经典148题

leetCode-98-Validate-Binary-Search-Tree

题目描述(中等难度)

leetCode-98-Validate-Binary-Search-Tree

输入一个树,判断该树是否是合法二分查找树,public boolean isValidBST(TreeNode root) { if (root == null) { return true; } boolean leftVailid = true; boolean rightVaild = true; if (root.left != null) { //大于左孩子并且左子树是合法二分查找树 leftVailid = root.val > root.left.val && isValidBST(root.left); } if (!leftVailid) { return false; } if (root.right != null) { //小于右孩子并且右子树是合法二分查找树 rightVaild = root.val < root.right.val && isValidBST(root.right); } return rightVaild; }

当然,这个解法没有通过。对于下面的解,结果利用上边的解法是错误的。

     10
    /  \
   5   15
      /  \
     6   20

虽然满足左子树是合法二分查找树,右子树是合法二分查找树,并且根节点大于左孩子,小于右孩子,但这个树不是合法的二分查找树。因为右子树中的 6 小于当前根节点 10。所以我们不应该判断「根节点大于左孩子,小于右孩子」,而是判断「根节点大于左子树中最大的数,小于右子树中最小的数」。

public boolean isValidBST(TreeNode root) {
    if (root == null || root.left == null && root.right == null) {
        return true;
    }
    //左子树是否合法
    if (isValidBST(root.left)) {
        if (root.left != null) {
            int max = getMaxOfBST(root.left);//得到左子树中最大的数
            if (root.val <= max) { //相等的情况,代表有重复的数字
                return false;
            }
        }

    } else {
        return false;
    }

    //右子树是否合法
    if (isValidBST(root.right)) {
        if (root.right != null) {
            int min = getMinOfBST(root.right);//得到右子树中最小的数
            if (root.val >= min) { //相等的情况,代表有重复的数字
                return false;
            }
        }

    } else {
        return false;
    }
    return true;
}

private int getMinOfBST(TreeNode root) {
    int min = root.val;
    while (root != null) {
        if (root.val <= min) {
            min = root.val;
        }
        root = root.left;
    }
    return min;
}

private int getMaxOfBST(TreeNode root) {
    int max = root.val;
    while (root != null) {
        if (root.val >= max) {
            max = root.val;
        }
        root = root.right;
    }
    return max;
}

解法二

来利用另一种思路,参考 10 / \ 5 15 / \ / 3 6 7 考虑 10 的范围 10(-inf,+inf) 考虑 5 的范围 10(-inf,+inf) / 5(-inf,10) 考虑 3 的范围 10(-inf,+inf) / 5(-inf,10) / 3(-inf,5) 考虑 6 的范围 10(-inf,+inf) / 5(-inf,10) / \ 3(-inf,5) 6(5,10) 考虑 15 的范围 10(-inf,+inf) / \ 5(-inf,10) 15(10,+inf) / \ 3(-inf,5) 6(5,10) 考虑 7 的范围,出现不符合返回 false 10(-inf,+inf) / \ 5(-inf,10) 15(10,+inf) / \ / 3(-inf,5) 6(5,10) 7(10,15)

可以观察到,左孩子的范围是 (父结点左边界,父节点的值),右孩子的范围是(父节点的值,父节点的右边界)。

还有个问题,java 里边没有提供负无穷和正无穷,用什么数来表示呢?

方案一,假设我们的题目的数值都是 Integer 范围的,那么我们用不在 Integer 范围的数字来表示负无穷和正无穷。用 long 去存储。

public boolean isValidBST(TreeNode root) {
    long maxValue = (long)Integer.MAX_VALUE + 1;
    long minValue = (long)Integer.MIN_VALUE - 1;
    return getAns(root, minValue, maxValue);
}

private boolean getAns(TreeNode node, long minVal, long maxVal) {
    if (node == null) {
        return true;
    }
    if (node.val <= minVal) {
        return false;
    }
    if (node.val >= maxVal) {
        return false;
    }
    return getAns(node.left, minVal, node.val) && getAns(node.right, node.val, maxVal);
}

方案二:传入 Integer 对象,然后 null 表示负无穷和正无穷。然后利用 JAVA 的自动装箱拆箱,数值的比较可以直接用不等号。

public boolean isValidBST(TreeNode root) {
    return getAns(root, null, null);
}

private boolean getAns(TreeNode node, Integer minValue, Integer maxValue) { 
    if (node == null) {
        return true;
    }
    if (minValue != null && node.val <= minValue) {
        return false;
    }
    if (maxValue != null && node.val >= maxValue) {
        return false;
    }
    return getAns(node.left, minValue, node.val) && getAns(node.right, node.val, maxValue);
}

解法三 DFS BFS

解法二其实就是树的 DFS,也就是二叉树的先序遍历,然后在遍历过程中,判断当前的值是是否在区间中。所以我们可以用栈来模拟递归过程。

public boolean isValidBST(TreeNode root) {
    if (root == null || root.left == null && root.right == null) {
        return true;
    }
    //利用三个栈来保存对应的节点和区间
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> minValues = new LinkedList<>();
    LinkedList<Integer> maxValues = new LinkedList<>();
    //头结点入栈
    TreeNode pNode = root;
    stack.push(pNode);
    minValues.push(null);
    maxValues.push(null);
    while (pNode != null || !stack.isEmpty()) {
        if (pNode != null) {
            //判断栈顶元素是否符合
            Integer minValue = minValues.peek();
            Integer maxValue = maxValues.peek();
            TreeNode node = stack.peek();
            if (minValue != null && node.val <= minValue) {
                return false;
            }
            if (maxValue != null && node.val >= maxValue) {
                return false;
            }
            //将左孩子加入到栈
            if(pNode.left!=null){
                stack.push(pNode.left);
                minValues.push(minValue);
                maxValues.push(pNode.val);
            }

            pNode = pNode.left;
        } else { // pNode == null && !stack.isEmpty()
            //出栈,将右孩子加入栈中
            TreeNode node = stack.pop();
            minValues.pop();
            Integer maxValue = maxValues.pop();
            if(node.right!=null){
                stack.push(node.right);
                minValues.push(node.val);
                maxValues.push(maxValue);
            }
            pNode = node.right;
        }
    }
    return true;
}

上边的 DFS 可以看出来一个缺点,就是我们判断完当前元素后并没有出栈,后续还会回来得到右孩子后才会出栈。所以其实我们可以用 BFS,利用一个队列,一层一层的遍历,遍历完一个就删除一个。

public boolean isValidBST(TreeNode root) {
    if (root == null || root.left == null && root.right == null) {
        return true;
    }
    //利用三个队列来保存对应的节点和区间
    Queue<TreeNode> queue = new LinkedList<>();
    Queue<Integer> minValues = new LinkedList<>();
    Queue<Integer> maxValues = new LinkedList<>();
    //头结点入队列
    TreeNode pNode = root;
    queue.offer(pNode);
    minValues.offer(null);
    maxValues.offer(null);
    while (!queue.isEmpty()) {
        //判断队列的头元素是否符合条件并且出队列
        Integer minValue = minValues.poll();
        Integer maxValue = maxValues.poll();
        pNode = queue.poll();
        if (minValue != null && pNode.val <= minValue) {
            return false;
        }
        if (maxValue != null && pNode.val >= maxValue) {
            return false;
        }
        //左孩子入队列
        if(pNode.left!=null){
            queue.offer(pNode.left);
            minValues.offer(minValue);
            maxValues.offer(pNode.val);
        }
        //右孩子入队列
        if(pNode.right!=null){
            queue.offer(pNode.right);
            minValues.offer(pNode.val);
            maxValues.offer(maxValue);
        } 
    }
    return true;
}

解法四 中序遍历

参考“>94 题中已经考虑过了。那么中序遍历在这里有什么好处呢?

中序遍历顺序会是左孩子,根节点,右孩子。二分查找树的性质,左孩子小于根节点,根节点小于右孩子。

是的,如果我们将中序遍历的结果输出,那么将会到的一个从小到大排列的序列。

所以我们只需要进行一次中序遍历,将遍历结果保存,然后判断该数组是否是从小到大排列的即可。

更近一步,由于我们只需要临近的两个数的相对关系,所以我们只需要在遍历过程中,把当前遍历的结果和上一个结果比较即可。

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;
}

这几天都是二叉树的相关题,主要是对前序遍历,中序遍历的理解,以及 DFS,如果再用好递归,利用栈模拟递归,题目就很好解了。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetCode-98-Validate-Binary-Search-Tree

链接:https://www.javajike.com/article/3234.html

« leetCode-97-Interleaving-String
leetcode-99-Recover-Binary-Search-Tree»

相关推荐

QR code