1. import java.util.ArrayList;
    3. /**
    4.  * 题目1. 返回一个树中子树为二叉搜索树的最大节点数
    5.  * 和题目2一个类型的题目
    6.  * 题目2. 给定一棵二叉树的头节点，返回这棵二叉树中最大的二叉搜索子树的头节点
    7.  */
    8. public class Code05_MaxSubBSTSize {
    10.     public static class Node {
    11.         public int value;
    12.         public Node left;
    13.         public Node right;
    15.         public Node(int data) {
    16.             this.value = data;
    17.         }
    18.     }
    20.     public static int getBSTSize(Node head) {
    21.         if (head == null) {
    22.             return 0;
    23.         }
    24.         ArrayList<Node> arr = new ArrayList<>();
    25.         in(head, arr);
    26.         for (int i = 1; i < arr.size(); i++) {
    27.             if (arr.get(i).value <= arr.get(i - 1).value) {
    28.                 return 0;
    29.             }
    30.         }
    31.         return arr.size();
    32.     }
    34.     public static void in(Node head, ArrayList<Node> arr) {
    35.         if (head == null) {
    36.             return;
    37.         }
    38.         in(head.left, arr);
    39.         arr.add(head);
    40.         in(head.right, arr);
    41.     }
    43.     public static int maxSubBSTSize1(Node head) {
    44.         if (head == null) {
    45.             return 0;
    46.         }
    47.         int h = getBSTSize(head);
    48.         if (h != 0) {
    49.             return h;
    50.         }
    51.         return Math.max(maxSubBSTSize1(head.left), maxSubBSTSize1(head.right));
    52.     }
    54. //    public static int maxSubBSTSize2(Node head) {
    55. //        if (head == null) {
    56. //            return 0;
    57. //        }
    58. //        return process(head).maxSubBSTSize;
    59. //    }
    60. //    
    61. //    
    62. //    
    63. //    
    64. //    
    65. //    
    66. //    
    67. //    
    68. //    
    69. //    // 任何子树
    70. //    public static class Info {
    71. //        public boolean isAllBST;
    72. //        public int maxSubBSTSize;
    73. //        public int min;
    74. //        public int max;
    75. //
    76. //        public Info(boolean is, int size, int mi, int ma) {
    77. //            isAllBST = is;
    78. //            maxSubBSTSize = size;
    79. //            min = mi;
    80. //            max = ma;
    81. //        }
    82. //    }
    83. //    
    84. //    
    85. //    
    86. //    
    87. //    public static Info process(Node X) {
    88. //        if(X == null) {
    89. //            return null;
    90. //        }
    91. //        Info leftInfo = process(X.left);
    92. //        Info rightInfo = process(X.right);
    93. //        
    94. //        
    95. //        
    96. //        int min = X.value;
    97. //        int max = X.value;
    98. //        
    99. //        if(leftInfo != null) {
    100. //            min = Math.min(min, leftInfo.min);
    101. //            max = Math.max(max, leftInfo.max);
    102. //        }
    103. //        if(rightInfo != null) {
    104. //            min = Math.min(min, rightInfo.min);
    105. //            max = Math.max(max, rightInfo.max);
    106. //        }
    107. //        
    108. //        
    109. //        
    110. //        
    111. //        
    112. //        
    113. //
    114. //        int maxSubBSTSize = 0;
    115. //        if(leftInfo != null) {
    116. //            maxSubBSTSize = leftInfo.maxSubBSTSize;
    117. //        }
    118. //        if(rightInfo !=null) {
    119. //            maxSubBSTSize = Math.max(maxSubBSTSize, rightInfo.maxSubBSTSize);
    120. //        }
    121. //        boolean isAllBST = false;
    122. //        
    123. //        
    124. //        if(
    125. //                // 左树整体需要是搜索二叉树
    126. //                (  leftInfo == null ? true : leftInfo.isAllBST    )
    127. //                &&
    128. //                (  rightInfo == null ? true : rightInfo.isAllBST    )
    129. //                &&
    130. //                // 左树最大值<x
    131. //                (leftInfo == null ? true : leftInfo.max < X.value)
    132. //                &&
    133. //                (rightInfo == null ? true : rightInfo.min > X.value)
    134. //                
    135. //                
    136. //                ) {
    137. //            
    138. //            maxSubBSTSize = 
    139. //                    (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
    140. //                    +
    141. //                    (rightInfo == null ? 0 : rightInfo.maxSubBSTSize)
    142. //                    +
    143. //                    1;
    144. //                    isAllBST = true;
    145. //            
    146. //            
    147. //        }
    148. //        return new Info(isAllBST, maxSubBSTSize, min, max);
    149. //    }
    151.     public static int maxSubBSTSize2(Node head) {
    152.         if(head == null) {
    153.             return 0;
    154.         }
    155.         return process(head).maxBSTSubtreeSize;
    156.     }
    158.     public static class Info {
    159.         public int maxBSTSubtreeSize;// 最大搜索字数的节点的个数
    160.         public int allSize;  // 整棵树的节点个数
    161.         public int max;   // 最大值
    162.         public int min;   // 最小值
    164.         public Info(int m, int a, int ma, int mi) {
    165.             maxBSTSubtreeSize = m;
    166.             allSize = a;
    167.             max = ma;
    168.             min = mi;
    169.         }
    170.     }
    172.     // 递归
    173.     public static Info process(Node x) {
    174.         // base case 不好设置，x为空时，最大值最小值不好设置，返回为空，交给上层处理
    175.         if (x == null) {
    176.             return null;
    177.         }
    179.         Info leftInfo = process(x.left);
    180.         Info rightInfo = process(x.right);
    182.         // 加工自己的信息属性
    183.         int max = x.value; // 最大值和最小值暂时设置为value
    184.         int min = x.value;
    185.         int allSize = 1;
    186.         if (leftInfo != null) {
    187.             max = Math.max(leftInfo.max, max);
    188.             min = Math.min(leftInfo.min, min);
    189.             allSize += leftInfo.allSize;
    190.         }
    191.         if (rightInfo != null) {
    192.             max = Math.max(rightInfo.max, max);
    193.             min = Math.min(rightInfo.min, min);
    194.             allSize += rightInfo.allSize;
    195.         }
    196.         // 可能性1
    197.         int p1 = -1;
    198.         if (leftInfo != null) {
    199.             p1 = leftInfo.maxBSTSubtreeSize;
    200.         }
    201.         // 可能性2 p2表示2可能情况下的maxSize，最大BST的节点个数
    202.         int p2 = -1;
    203.         if (rightInfo != null) {
    204.             p2 = rightInfo.maxBSTSubtreeSize;
    205.         }
    206.         // 可能性3  x作为最大BST的头节点  null节点默认为搜索二叉树
    207.         int p3 = -1;
    208.         boolean leftBST = leftInfo == null ? true : (leftInfo.maxBSTSubtreeSize == leftInfo.allSize);  //
    209.         boolean rightBST = rightInfo == null ? true : (rightInfo.maxBSTSubtreeSize == rightInfo.allSize);
    210.         if (leftBST && rightBST) {  // 左树整体是BST并且右侧整体是BST
    211.             boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.value);
    212.             boolean rightMinMoreX = rightInfo == null ? true : (x.value < rightInfo.min);
    213.             if (leftMaxLessX && rightMinMoreX) {  // 左树最大值 < x 并且右树最小值 >  x
    214.                 int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
    215.                 int rightSize = rightInfo == null ? 0 : rightInfo.allSize;
    216.                 p3 = leftSize + rightSize + 1;  // maxSize
    217.             }
    218.         }
    220.         // 最后比较求最大的maxSize
    221.         int maxBSTSubtreeSize = Math.max(p1, Math.max(p2, p3));
    222.         return new Info(maxBSTSubtreeSize, allSize, max, min);
    223.     }
    225.     // for test
    226.     public static Node generateRandomBST(int maxLevel, int maxValue) {
    227.         return generate(1, maxLevel, maxValue);
    228.     }
    230.     // for test
    231.     public static Node generate(int level, int maxLevel, int maxValue) {
    232.         if (level > maxLevel || Math.random() < 0.5) {
    233.             return null;
    234.         }
    235.         Node head = new Node((int) (Math.random() * maxValue));
    236.         head.left = generate(level + 1, maxLevel, maxValue);
    237.         head.right = generate(level + 1, maxLevel, maxValue);
    238.         return head;
    239.     }
    241.     public static void main(String[] args) {
    242.         int maxLevel = 4;
    243.         int maxValue = 100;
    244.         int testTimes = 1000000;
    245.         for (int i = 0; i < testTimes; i++) {
    246.             Node head = generateRandomBST(maxLevel, maxValue);
    247.             if (maxSubBSTSize1(head) != maxSubBSTSize2(head)) {
    248.                 System.out.println("Oops!");
    249.             }
    250.         }
    251.         System.out.println("finish!");
    252.     }
    254. }