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; linkedListinOrderList = 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); } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)