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

1.1第一种解法

先序遍历的方式：先序遍历每个节点，获取以当前节点为头的情况下的最大BST拓扑结构，并记录最大值

    public int bstTopoSize1(Node head){
        if(head == null) return 0;
        int max = maxTopo(head,head);
        max = Math.max(bstTopoSize1(head.left), max);
        max = Math.max(bstTopoSize1(head.right), max);
        return max;
    }
    
    
    public int maxTopo(Node h,Node n){
        if( h!=null && n!=null && isBSTNode(h,n,n.value)){
            return maxTopo(h, n.left) + maxTopo(h, n.right) + 1;
        }
        return 0;
    }
    
    //当以h开头的时候，n在不在搜索二叉树上
    public boolean isBSTNode(Node h,Node n,int value){
        if(h == null)//没有在搜索二叉树上找到
            return false;
        if(h == n)//通过左右移动找到
            return true;
        return isBSTNode(h.value>value?h.left:h.right, n, value);
    }

1.2第二种解法

后序遍历的方式：后序遍历，先获取到左右子树的情况，然后再通过左右子树的情况来更新当前节点

为什么左子树只需要对左子树的右边界进行过滤更新，为什么右子树只需要对右子树的左边界进行过滤更新？
假设已经左右子树已经完成了贡献记录的更新，这个时候，左子树就是一个BST，所以左子树的右边界在不断的增大，由于这个子树只能保证所有的右边界大于左子树的头结点；同时左边界都小于左子树的头结点，所以，需要更新的只有不符合以head为头结点的情况下可能会出现大于head节点的情况，因此只有右边界可能出现大于head节点的情况，所以，在modifyMap的时候，如果是左子树，只需考察右边界，在右边界上有节点大于head节点的时候去更新右边界。
右子树也是同理，只有左边界上可能出现小于head节点的节点，这种节点会破坏原来右子树的记录，所以需要更新。

流程:

    public static int bstTopoSize2(Node head) {
        Map<Node, Record> map = new HashMap<Node, Record>();
        return posOrder(head, map);
    }

    public static int posOrder(Node h, Map<Node, Record> map) {
        if (h == null) {
            return 0;
        }
                //获取左右子树的
        int ls = posOrder(h.left, map);
        int rs = posOrder(h.right, map);
                //在以value为头的情况下更新
        modifyMap(h.left, h.value, map, true);
        modifyMap(h.right, h.value, map, false);
                //根据记录更新head的数据
        Record lr = map.get(h.left);
        Record rr = map.get(h.right);
        int lbst = lr == null ? 0 : lr.l + lr.r + 1;
        int rbst = rr == null ? 0 : rr.l + rr.r + 1;
                //保存数据
        map.put(h, new Record(lbst, rbst));
                //获取最大的情况
        return Math.max(lbst + rbst + 1, Math.max(ls, rs));
    }
        //根据左右来更新
        
    public static int modifyMap(Node n, int v, Map<Node, Record> m, boolean s) {
        if (n == null || (!m.containsKey(n))) {
            return 0;
        }
        Record r = m.get(n);
        if ((s && n.value > v) || ((!s) && n.value < v)) {
            m.remove(n);
            return r.l + r.r + 1;
        } else {
            int minus = modifyMap(s ? n.right : n.left, v, m, s);
            if (s) {
                r.r = r.r - minus;
            } else {
                r.l = r.l - minus;
            }
            m.put(n, r);
            return minus;
        }
    }