Validate Binary Search Tree

Leave a comment

November 30, 2016 by oneOokay

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.

Example 1:

    2
   / \
  1   3

Binary tree [2,1,3], return true.

Example 2:

    1
   / \
  2   3

Binary tree [1,2,3], return false.


Iterative:

  • 很容易的想到了iterative preorder 遍历BST方法,但是点在于如何定最小值.
  • 想到了用一个pre来存前者.但是我错的地方在于,用了int pre导致我必须给pre赋值,用Integer.MAX_VALUE和Integer.MIN_VALUE的话会遇到corner case过不去.
  • 所以这里应该用TreeNode pre 或者Integer pre.这两个pre都可以初始化为null. 当pre为null的时候就不需要进行比较.

Recursive:

首先isValidBST本身不是一个可以用来作为recursive的method,因为只有一个param,我们判断BST有大小关系,至少需要两个params. 然后试了有两个params的helper method,还是不行.

这里应该是用有三个params的help method来进行递归.

  • helper(TreeNode node, Integer min, Integer max)

//Iterative
public boolean isValidBST(TreeNode root) {
        if (root == null) return true;        
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode pre = null;
        while (root != null || !s.isEmpty()){
            while (root != null){
                s.push(root);
                root = root.left;
            }
            root = s.pop();
            if (pre!= null && pre.val >= root.val) return false;
            pre = root;
            root = root.right;
        }
        return true;
    }
//recursive
public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }
    
    private boolean helper(TreeNode root, Integer min, Integer max){
        if (root == null) return true;
        if (min != null && root.val <= min || max != null && root.val >= max)
            return false;
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }

相关的题目是:Kth Smallest Element in a BST

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: