Determine if a given binary tree is binary search tree.

Assumptions

  • There are no duplicate keys in binary search tree.
  • You can assume the keys stored in the binary search tree can not be Integer.MIN_VALUE or Integer.MAX_VALUE.

Corner Cases

  • What if the binary tree is null? Return true in this case.

//思路:BST的话,每个节点的值要在范围内,所以可以recursively把value从上往下传

//time: 每一层call recursion function两次,所以2+4+8+... = O(n)

//space: 每一层是O(1),所以是O(height) (height = logn if balanced, height = n if unbalanced)

  public boolean isBST(TreeNode root) {
    return helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
  }
  private boolean helper(TreeNode root, int min, int max) {
    if (root == null) {
      return true;
    }
    if (root.key < min || root.key > max) {
      return false;
    }
    return helper(root.left, min, root.key - 1) && helper(root.right, root.key + 1, max);
  }

results matching ""

    No results matching ""