找到二叉树中的最大搜索二叉子树

1. 子树的最大二叉搜索树的根结点；
2. 子树的最大二叉搜索树的节点数量；
3. 子树是否是二叉搜索树；
4. 子树的节点最小值；
5. 子树的节点最大值。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

class Info {
    public TreeNode maxBSTHead;
    public int maxBSTSize;
    public boolean isBST;
    public int min;
    public int max;
    public Info(TreeNode maxBSTHead, int maxBSTSize, boolean isBST, int min, int max) {
        this.maxBSTHead = maxBSTHead;
        this.maxBSTSize = maxBSTSize;
        this.isBST = isBST;
        this.min = min;
        this.max = max;
    }
}

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashMap<Integer, TreeNode> map = new HashMap<>();
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), rootVal = Integer.parseInt(params[1]);
        // 构建二叉树
        TreeNode root = new TreeNode(rootVal);
        map.put(rootVal, root);
        for(int i = 0; i < n; i++){
            params = br.readLine().split(" ");
            int nodeVal = Integer.parseInt(params[0]);
            int leftVal = Integer.parseInt(params[1]);
            int rightVal = Integer.parseInt(params[2]);
            TreeNode node = map.get(nodeVal);
            if(leftVal != 0) {
                node.left = new TreeNode(leftVal);
                map.put(leftVal, node.left);
            }
            if(rightVal != 0) {
                node.right = new TreeNode(rightVal);
                map.put(rightVal, node.right);
            }
        }
        // 求解
        System.out.println(process(root).maxBSTSize);
    }
    
    private static Info process(TreeNode node) {
        if(node == null) return null;
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        TreeNode maxBSTHead = null;
        int maxBSTSize = 0;
        int max = node.val;
        int min = node.val;
        // 最值在左右信息不为空的时候需要比较更新
        if(leftInfo != null){
            maxBSTHead = leftInfo.maxBSTHead;
            maxBSTSize = leftInfo.maxBSTSize;
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
        }
        if(rightInfo != null){
            if(rightInfo.maxBSTSize > maxBSTSize){
                maxBSTHead = rightInfo.maxBSTHead;
                maxBSTSize = rightInfo.maxBSTSize;
            }
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
        }
        boolean isBST = false;
        // 左右子树都是BST且能够和当前节点连起来时，能够形成一个以当前节点为根的更大的BST
        if((leftInfo == null || (leftInfo.isBST && leftInfo.max < node.val)) && (rightInfo == null || (rightInfo.isBST && rightInfo.min > node.val))){
            isBST = true;
            maxBSTHead = node;
            maxBSTSize = (leftInfo != null? leftInfo.maxBSTSize: 0) + (rightInfo != null? rightInfo.maxBSTSize: 0) + 1;
        }
        return new Info(maxBSTHead, maxBSTSize, isBST, min, max);
    }
}