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

import java.util.*;

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

    /*
    记录节点贡献值：对每一个节点生成（a, b）其中a代表当前节点左子树在二叉树的拓扑结构中可以给你贡献几个节点，
    同理b表示。。。。。右子树。。。。。
    采取后序遍历的形式从下往上设置贡献值，若换头节点了，先查左右子节点是否符合二叉树，后查左子节点的右子树和右子节点的左子树
    */
    class Record {
        public int l;
        public int r;
        public Record (int l, int r) {
            this.l = l;
            this.r = r;
        }
    }

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node head = constructTree(sc, n);
        int result = returnSize(head);
        System.out.println(result);
    }
    
    public static Node constructTree (Scanner sc, int n) {
        HashMap<Integer, Node> map = new HashMap<>();
        int rootVal = sc.nextInt();
        Node root = new Node(rootVal);
        map.put(rootVal, root);
        for (int i = 0; i < n; i++) {
            int nodeVal = sc.nextInt();
            int leftVal = sc.nextInt();
            int rightVal = sc.nextInt();
            if (map.containsKey(nodeVal)) {
                Node tmpNode = map.get(nodeVal);
                Node leftNode = leftVal == 0 ? null : new Node(leftVal);
                Node rightNode = rightVal == 0 ? null : new Node(rightVal);
                tmpNode.left = leftNode;
                tmpNode.right = rightNode;
                if (leftVal != 0)
                    map.put(leftVal, leftNode);
                if (rightVal != 0)
                    map.put(rightVal, rightNode);
            }
        }
        return root;
    }
    /*
    //此方法时间复杂度为O(N^2), 因为要以n个点为头，
    //且每次找最大拓扑结构都需要查找O(N)个节点.
    public static int returnSize(Node head) {
        if (head == null)
            return 0;
        //假设拓扑结构也以整棵树头节点为头节点，找出最大符合二叉树的拓扑结构
        int max = maxTopo(head, head);
        //接着以每一个节点为头找最大结构
        max = Math.max(returnSize(head.left), max);
        max = Math.max(returnSize(head.right), max);
        return max;
    }
    
    //找到以h为头节点的树***有多少个节点符合BST结构
    public static int maxTopo(Node head, Node node) {
        if (head != null && node != null && isBSTNode(head, node)) 
            return maxTopo(head, node.left) + maxTopo(head, node.right) + 1;
        return 0;
    }
    
    //判断以head为头节点的树种node是不是一个可用的BST节点
    public static boolean isBSTNode (Node head, Node node) {
        if (head == null)
            return false;
        if (head == node)
            return true;
        return isBSTNode(head.val > node.val ? head.left : head.right, node);
    }
    */
    
    /*此方法时间复杂度为O(N)。主旨是对任何一个节点，遍历这个节点的左子树的右边界和
    右子树的左边界。所有右边界和左边界的所有节点数量为O(N), 所有遍历的代价为O(N),所以
    方法时间复杂度为O(N).
    */
    //把节点与贡献值对应
    public static int returnSize(Node head) {
        Map<Node, Record> map = new HashMap<Node, Record>();
        return posOrder(head, map);
    }
    //后序遍历返回以head为头节点的树的所有子树中最大二叉树拓扑结构的节点数量
    public static int posOrder (Node head, Map<Node, Record> map) {
        if (head == null) {
            return 0;
        }
        //先获得head左右子树上最大二叉树拓扑结构节点数
        int ls = posOrder(head.left, map);
        int rs = posOrder(head.right, map);
        //然后修改map，看以head为头时还有多少个有效节点
        modifyMap(head.left, head, map, true);
        modifyMap(head.right, head, map, false);
        //lr和rr分别记录以head左孩子和右孩子为头的左右二叉树，
        //这两棵二叉树的左右子树分别能给自己提供多少个有效节点
        Record lr = map.get(head.left);
        Record rr = map.get(head.right);
        //左右孩子整体能提供多少的有效节点
        int lbst = lr == null ? 0 : lr.l + lr.r + 1;
        int rbst = rr == null ? 0 : rr.l + rr.r + 1;
        map.put(head, new Record(lbst, rbst));
        //返回包括head的整个子树最多能提供多少个有效节点
        return Math.max(Math.max(ls, rs), lbst + rbst + 1);
    }
    
    //isLeft表示node节点是否在parent的左子树上
    //返回的值表示有几个node需要被忽略（无效node）
    public static int modifyMap(Node child, Node parent, Map<Node, Record> m, boolean isLeft) {
        if (child == null || (!m.containsKey(child)))
            return 0;
        Record r = m.get(child);
        //当node无法作为以parent为头的树的有效节点时
        if ((isLeft && child.val > parent.val) || (!isLeft) && child.val < parent.val) {
            //一旦当前child违反规则了，则不用再考虑它以及它的所有孩子们了，从map中移除掉
            //同时告诉我以它为头节点的整棵二叉树有多少个node
            m.remove(child);
            return r.l +r.r + 1;
        }
        else {
            /*若当前child点是否为有效节点，看当前节点在head的左子树上还是右子树上
            若在左子树上，child的左孩子们就都不用再查了，肯定都比head小，所以查child的右孩子；
            若在右子树上则child右孩子们都不用再查了，肯定都比head大，所以查child的左孩子。
            */
            int minus = modifyMap(isLeft ? child.right : child.left, parent, m, isLeft);
            if (isLeft) 
                r.r = r.r - minus;
            else
                r.l = r.l - minus;
            m.put(child, r);
            return minus;
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
bool isBST(int root,int target,int* lc,int* rc)
{
    if(!root) return false;
    if(root==target) return true;
    return isBST(root > target ? lc[root]:rc[root],target,lc,rc);
}
int maxTopo(int root_1,int root_2,int* lc,int* rc)
{
    if(root_1 && root_2 && isBST(root_1,root_2,lc,rc))
        return maxTopo(root_1,lc[root_2],lc,rc) + maxTopo(root_1,rc[root_2],lc,rc) + 1;
    return 0;
}
void visit(int root,int* lc,int* rc,int& ans)
{
    if(!root) return;
    ans = max(ans,maxTopo(root,root,lc,rc));
    visit(lc[root],lc,rc,ans);
    visit(rc[root],lc,rc,ans);
}
int main()
{
    int n,root;
    cin>>n>>root;
    int p;
    int* lc = new int[n+1];
    int* rc = new int[n+1];
    for(int i=0;i<n;++i)
    {
        cin>>p;
        cin>>lc[p]>>rc[p];
    }
    int ans = 0;
    visit(root,lc,rc,ans);
    cout<<ans<<endl;
    return 0;
}