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

import java.io.*;
import java.util.*;

public class Main {

    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    static class Info {
        boolean isBST;  // 当前树是否是二叉搜索树
        int size;       // 当前树的大小（节点数）
        int min;        // 当前树的最小值
        int max;        // 当前树的最大值
        Info(boolean isBST, int size, int min, int max) {
            this.isBST = isBST;
            this.size = size;
            this.min = min;
            this.max = max;
        }
    }

    static Map<Integer, TreeNode> nodeMap = new HashMap<>();
    static Map<Integer, int[]> childrenMap = new HashMap<>();
    static TreeNode root = null;
    static int maxNodes = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int rootVal = Integer.parseInt(firstLine[1]);

        // 初始化二叉树节点
        for (int i = 0; i < n; i++) {
            //建树时借助了hashMap
            String[] line = br.readLine().split(" ");
            int fa = Integer.parseInt(line[0]);
            int lch = Integer.parseInt(line[1]);
            int rch = Integer.parseInt(line[2]);

            if (!nodeMap.containsKey(fa)) {
                nodeMap.put(fa, new TreeNode(fa));
            }
            TreeNode node = nodeMap.get(fa);
            if (lch != 0) {
                if (!nodeMap.containsKey(lch)) {
                    nodeMap.put(lch, new TreeNode(lch));
                }
                node.left = nodeMap.get(lch);
            }
            if (rch != 0) {
                if (!nodeMap.containsKey(rch)) {
                    nodeMap.put(rch, new TreeNode(rch));
                }
                node.right = nodeMap.get(rch);
            }
        }

        root = nodeMap.get(rootVal);

        // 使用递归来计算最大搜索二叉子树
        findLargestBST(root);

        // 输出结果
        System.out.println(maxNodes);
    }

    // 后序遍历来处理每个节点，返回子树的信息
    public static Info findLargestBST(TreeNode node) {
        if (node == null) {
            return new Info(true, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }

        // 递归计算左右子树
        Info leftInfo = findLargestBST(node.left);
        Info rightInfo = findLargestBST(node.right);

        // 当前树是否是搜索二叉树的判断
        if (leftInfo.isBST && rightInfo.isBST && node.val > leftInfo.max &&
                node.val < rightInfo.min) {
            // 当前节点是搜索二叉树
            int size = leftInfo.size + rightInfo.size + 1;
            maxNodes = Math.max(maxNodes, size);  // 更新最大节点数
            return new Info(true, size, Math.min(node.val, leftInfo.min), Math.max(node.val,
                            rightInfo.max));
        } else {
            // 当前节点不是搜索二叉树
            return new Info(false, Math.max(leftInfo.size, rightInfo.size), 0, 0);
        }
    }
}