判断是否是搜索二叉树

判断是否是搜索二叉树

import java.util.linkedList;
import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock;
public class IsBST {
  public static class Node {
    public int value;
    public Node left;
    public Node right;

    Node(int value) { this.value = value; }
  }
  //是否是搜索二叉树
  //方式一
  public static boolean isBST(Node head) {
    if (head == null)
      return true;
    linkedList inOrderList = new linkedList();
    process(head, inOrderList);
    int pre = Integer.MIN_VALUE;
    for (Node cur : inOrderList) {
      if (pre >= cur.value) {
        return false;
      }
      pre = cur.value;
    }
    return true;
  }

  public static void process(Node node, linkedList inOrderList) {
    if (node == null)
      return;
    process(node.left, inOrderList);
    inOrderList.add(node);
    process(node, inOrderList);
  }
  //方式二
  public static int prevalue = Integer.MIN_VALUE;
  public static boolean _isBST(Node head) {
    if (head == null)
      return true;
    boolean isLeftBST = _isBST(head.left);
    if (!isLeftBST)
      return false;
    if (head.value <= prevalue) {
      return false;
    } else {
      prevalue = head.value;
    }
    return _isBST(head.right);
  }
}

方法二

public class A {
  public static class Node {
    public int data;
    public Node right;
    public Node left;

    Node(int data) { this.data = data; }
  }

  public static class ReturnData {
    public boolean isBST;
    public int min;
    public int max;

    ReturnData(boolean isBST, int min, int max) {
      this.isBST = isBST;
      this.min = min;
      this.max = max;
    }
  }

  public static ReturnData isBST(Node x) {
    if (x == null)
      return null;
    ReturnData leftdata = process(x.left);
    ReturnData rightdata = process(x.right);
    boolean isBST = true;
    int min = x.value;
    int max = x.value;
    if (leftdata != null) {
      min = Math.min(min, leftdata.min);
      max = Math.max(max, leftdata.max);
    }
    if (rightdata != null) {
      min = Math.min(min, rightdata.min);
      max = Math.max(max, rightdata.max);
    }
    if (leftdata != null && (!leftdata.isBST || leftdata.max >= x.value)) {
      isBST = false;
    }
    if (rightdata != null && (!rightdata.isBST || rightdata.min <= x.value)) {
      isBST = false;
    }
    return new ReturnData(isBST, min, max);
  }
}