首页 > ACM题库 > LeetCode > Validate Binary Search Tree[Leetcode]二分查找树的判定
2014
11-18

Validate Binary Search Tree[Leetcode]二分查找树的判定

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees

给定一棵树,判断其是否是一颗二分查找树。

方法一 中序遍历

因为一棵二叉搜索树的中序遍历后其结点值是从小到大排好序的,所以依此给出下面的解法。该解法时间复杂度也是O(n)。

使用一个指针指向遍历的当前节点的前一个节点。

public class ValidateBinarySearchTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    static class NodeWrapper{
        TreeNode node;
    }
    public boolean isValidBST(TreeNode root) {
        return helper(root, new NodeWrapper());
    }

    boolean helper(TreeNode root, NodeWrapper pre){
        if(root == null)
            return true;
        if(!helper(root.left, pre))
            return false;
        //判断当前节点和上一个节点是否是有序的
        if(pre.node != null && root.val <= pre.node.val) return false;
        pre.node = root;
        return helper(root.right, pre);
    }

    public static void main(String args[]){
        TreeNode root = new TreeNode(7);
        root.left = new TreeNode(5);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(6);
        root.right.left = new TreeNode(9);
        root.right.right = new TreeNode(12);

        ValidateBinarySearchTree v = new ValidateBinarySearchTree();
        System.out.println(v.isValidBST(root));
    }

}

 方法二  根据定义递归判断

  • 结点node的左子树所有结点的值都小于node的值。
  • 结点node的右子树所有结点的值都大于node的值。
  • 结点node的左右子树同样都必须是二叉搜索树。

以下面的树为例,虽然tree(1)是合法的二分查找树,但是6小于10,  6所在的位置应该是位于 10~15之间,所以这棵树是不合法的。也就是说,需要两个值maxValue, minValue 来记录当前节点应该的取值范围。

   10 ----- binary tree (0)
   /  \
  5   15     -------- binary tree (1)
     /  \
    6    20

代码如下:

public boolean isValidBST2(TreeNode root){
        return helper2( root, Integer.MAX_VALUE, Integer.MIN_VALUE);
    }

    private boolean helper2(TreeNode root, int maxValue, int minValue) {
        if(root == null) return true;
        if(root.val >= maxValue || root.val <= minValue) return false;
        return helper2(root.left, root.val, minValue) && helper2(root.right, maxValue, root.val);
    }

两中方法的复杂度都为O(n).


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。