1. import java.util.ArrayList;
    3. /**
    4.  * 判断树是否为搜索二叉树
    5.  */
    6. public class Code02_IsBST {
    8.     public static class Node {
    9.         public int value;
    10.         public Node left;
    11.         public Node right;
    13.         public Node(int data) {
    14.             this.value = data;
    15.         }
    16.     }
    18.     public static boolean isBST1(Node head) {
    19.         if (head == null) {
    20.             return true;
    21.         }
    22.         ArrayList<Node> arr = new ArrayList<>();
    23.         in(head, arr);
    24.         for (int i = 1; i < arr.size(); i++) {
    25.             if (arr.get(i).value <= arr.get(i - 1).value) {
    26.                 return false;
    27.             }
    28.         }
    29.         return true;
    30.     }
    32.     public static void in(Node head, ArrayList<Node> arr) {
    33.         if (head == null) {
    34.             return;
    35.         }
    36.         in(head.left, arr);
    37.         arr.add(head);
    38.         in(head.right, arr);
    39.     }
    41.     // *****************************************************************************
    43.     /**
    44.      * 主函数
    45.      * @param head
    46.      * @return
    47.      */
    48.     public static boolean isBST2(Node head) {
    49.         // 在这里处理空，将下层的空放在这里处理
    50.         if (head == null) {
    51.             return true;
    52.         }
    53.         return process(head).isBST;
    54.     }
    56.     /**
    57.      * 信息体定义
    58.      */
    59.     public static class Info {
    60.         public boolean isBST;
    61.         public int max;
    62.         public int min;
    63.         public Info(boolean i, int ma, int mi) {
    64.             isBST = i;
    65.             max = ma;
    66.             min = mi;
    67.         }
    68.     }
    70.     /**
    71.      * 递归，所有过程一视同仁，必须返回信息体Info
    72.      * @param x
    73.      * @return
    74.      */
    75.     public static Info process(Node x) {
    77.         // base case 对于节点为空时，如果不知道如何设置信息体中的值，可以返回空，然后在上游来处理这个空null；最大值和最小值知道如何设置，返回空
    78.         if (x == null) {
    79.             return null;
    80.         }
    82.         // 向左右树索取信息体信息
    83.         Info leftInfo = process(x.left);
    84.         Info rightInfo = process(x.right);
    86.         // 加工自己的信息体内容
    87.         // 1、加工 Info-max
    88.         int max = x.value; // 首先设置自己值为最大值
    89.         if (leftInfo != null) {  // 如果左树不为空，将左树中的最大值和当前max比较
    90.             max = Math.max(max, leftInfo.max);
    91.         }
    92.         if (rightInfo != null) { // 如果右树不为空，将右树中的最大值和当前max比较
    93.             max = Math.max(max, rightInfo.max);
    94.         }
    95.         // 2、加工 Info-min 最小值
    96.         int min = x.value;
    97.         if (leftInfo != null) {
    98.             min = Math.min(min, leftInfo.min);
    99.         }
    100.         if (rightInfo != null) {
    101.             min = Math.min(min, rightInfo.min);
    102.         }
    104.         // 3、加工 Info-isBST，这时候由于null是没有判断的，放在上层判断，因此要充分考虑为空的情况。
    105.         boolean isBST = true; //先假定是搜索二叉树，然后判断以下条件是否违反，违反了重置isBST
    106.         if (leftInfo != null && !leftInfo.isBST) {
    107.             isBST = false;
    108.         }
    109.         if (rightInfo != null && !rightInfo.isBST) {
    110.             isBST = false;
    111.         }
    112.         if (leftInfo != null && leftInfo.max >= x.value) {
    113.             isBST = false;
    114.         }
    115.         if (rightInfo != null && rightInfo.min <= x.value) {
    116.             isBST = false;
    117.         }
    118.         return new Info(isBST, max, min);
    119.     }
    121.     //#########################对数器##############################################
    123.     // for test
    124.     public static Node generateRandomBST(int maxLevel, int maxValue) {
    125.         return generate(1, maxLevel, maxValue);
    126.     }
    128.     // for test
    129.     public static Node generate(int level, int maxLevel, int maxValue) {
    130.         if (level > maxLevel || Math.random() < 0.5) {
    131.             return null;
    132.         }
    133.         Node head = new Node((int) (Math.random() * maxValue));
    134.         head.left = generate(level + 1, maxLevel, maxValue);
    135.         head.right = generate(level + 1, maxLevel, maxValue);
    136.         return head;
    137.     }
    139.     public static void main(String[] args) {
    140.         int maxLevel = 4;
    141.         int maxValue = 100;
    142.         int testTimes = 1000000;
    143.         for (int i = 0; i < testTimes; i++) {
    144.             Node head = generateRandomBST(maxLevel, maxValue);
    145.             if (isBST1(head) != isBST2(head)) {
    146.                 System.out.println("Oops!");
    147.             }
    148.         }
    149.         System.out.println("finish!");
    150.     }
    152. }