找到二叉树中符合搜索二叉树条件的最大拓扑结构

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 Record {
    public int left;       // 左孩子贡献的BST节点数
    public int right;      // 右孩子贡献的BST节点数
    public Record(int left, int right) {
        this.left = left;
        this.right = right;
    }
}

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(maxBstTopoSize(root));
    }
    
    private static int maxBstTopoSize(TreeNode head) {
        HashMap<TreeNode, Record> map = new HashMap<>();      // 用于存储各个节点的拓扑贡献记录
        return postOrder(head, map);
    }
    
    private static int postOrder(TreeNode head, HashMap<TreeNode, Record> map) {
        if(head == null) return 0;
        int leftSize = postOrder(head.left, map);
        int rightSize = postOrder(head.right, map);
        // 检查头结点能够囊括左右孩子多少节点，并修改孩子节点的贡献记录
        modifyMap(head.left, head.val, map, true);
        modifyMap(head.right, head.val, map, false);
        // 获得左右孩子的贡献记录
        Record leftRecord = map.get(head.left);
        Record rightRecord = map.get(head.right);
        // 计算左右孩子贡献的BST节点数
        int leftBST = leftRecord == null? 0: leftRecord.left + leftRecord.right + 1;
        int rightBST = rightRecord == null? 0: rightRecord.left + rightRecord.right + 1;
        map.put(head, new Record(leftBST, rightBST));
        return Math.max(leftBST + rightBST + 1, Math.max(leftSize, rightSize));
    }
    
    public static int modifyMap(TreeNode node, int rootVal, HashMap<TreeNode, Record> map, boolean isLeftTree) {
        if(node == null || (!map.containsKey(node))) return 0;
        Record record = map.get(node);      // 获得当前节点node的拓扑贡献记录
        if((isLeftTree && node.val > rootVal) || ((!isLeftTree) && node.val < rootVal)){
            // 如果左树的右边界节点node比根的值大，或者右树的左边界节点node比根的值小，就移除node的贡献
            map.remove(node);
            return record.left + record.right + 1;       // 要把node节点及其孩子节点的贡献返回去让上层节点删除掉
        }else{
            // 是左树就递归检查右边界，是右树就递归检查左边界
            int minus = modifyMap(isLeftTree? node.right: node.left, rootVal, map, isLeftTree);
            // 沿途修改边界节点node的贡献记录
            if(isLeftTree){
                record.right = record.right - minus;
            }else{
                record.left = record.left - minus;
            }
            map.put(node, record);
            return minus;
        }
    }
}