【题目】
给定一颗二叉树的头结点head，已知其中所有节点的值都不一样，找到含有节点最多的搜索二叉树，并返回这棵子树的头结点
package zyc.binaryTree;/*** 找到二叉树中的最大搜索二叉树*/
public class P121_maxBst {public static void main(String[] args) {Node node = new Node(10);node.left = new Node(4);node.left.left = new Node(2);node.left.right = new Node(5);node.right = new Node(14);node.right.left = new Node(11);node.right.right = new Node(15);ReturnType maxBst = getMaxBst(node);Node bstHead = maxBst.bstHead;System.out.println(bstHead.value + " " + maxBst.maxSize);}public static ReturnType getMaxBst(Node node) {if (node == null) {// base case, 如果子树为空，最小值为系统最大，最大值为系统最小return new ReturnType(null, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);}ReturnType leftData = getMaxBst(node.left);ReturnType rightData = getMaxBst(node.right);int max = Integer.max(node.value, Integer.max(leftData.max, rightData.max));int min = Integer.min(node.value, Integer.min(leftData.min, rightData.min));// 第一种情况，node 的 子树为最大搜索树int maxSize = Math.max(leftData.maxSize, rightData.maxSize);Node bstHead = leftData.maxSize > rightData.maxSize ? leftData.bstHead : rightData.bstHead;// 第二种情况，左子树最大搜索树就是左子树全体，且左子树的最大值小于node.value,右子树的最大搜索树就是右子树全体，且右子树的最小值大于node.valueif (leftData.bstHead == node.left && leftData.max < node.value && rightData.bstHead == node.right && rightData.min > node.value) {maxSize = leftData.maxSize + rightData.maxSize + 1;bstHead = node;}return new ReturnType(bstHead, maxSize, max, min);}public static class ReturnType {// 最大搜索树头结点public Node bstHead;// 节点个数public int maxSize;// 最大值public int max;// 最小值public int min;public ReturnType(Node bstHead, int maxSize, int max, int min) {this.bstHead = bstHead;this.maxSize = maxSize;this.max = max;this.min = min;}}public static class Node {public int value;public Node left;public Node right;public Node(int value) {this.value = value;}}}