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

static class Node{
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }
    }

    /*
    1. 分析
    树形动态规划问题的前提：如果题目要求的目标是规则S，则流程一般是完成每个结点为root时的子树，在规则S下的每一个答案，
    最终答案一定在这些答案中。本题中，规则是整棵树的最大搜索二叉树（maxBST）。
    求出每一个节点作为root的子树的maxBST，最终答案一定在其中。

    1.1 第一步，可能性分析
    情况1：maxBST来自（注意，不是 “是“）X的左子树。
    情况2：maxBST来自X的右子树。
    情况3：X为root的树本身是maxBST。这需要两个条件。
        条件1，X的左子树和右子树都是maxBST。
        条件2，X.val 比左子树的val都大，比右子树的都小。
    1.2 第二步，列出信息
    根据可能性，列出所有需要的信息。为了分析前两个可能，需要左右子树上各自的maxBST的头部、大小。
    为了分析第三种可能，还需要当前结点X的值与左子树所有结点的最大值、右子树所有结点的最小值的大小。

    1.3 第三步，合并信息

    * */
    static class ReturnType{
        public Node maxBSTHead;
        public int maxBSTSize;
        public int max;
        public int min;

        public ReturnType(Node maxBSTHead, int maxBSTSize, int min, int max) {
            this.maxBSTHead = maxBSTHead;
            this.maxBSTSize = maxBSTSize;
            this.min = min;
            this.max = max;
        }
    }

    /*1、4：设计递归函数
    递归函数是处理以X为节点的情况下的***括设计递归的base case，默认直接得到左树和右树 的所有信息，
    以及把可能性做整合，并且要返回第三步的信息结构 这4个小步骤
    * */
    public static ReturnType process(Node X){
        //base case:如果子树是空树
        //min为MAX_VALUE, 保证所有的val都比它小
        //max反之
        if(X==null){
            return new ReturnType(null,0,Integer.MAX_VALUE,Integer.MIN_VALUE);
        }

        //2.1、默认得到左树的全部信息
        ReturnType lData=process(X.left);
        //2.2、默认得到右树的全部信息
        ReturnType rData=process(X.right);

        //3、信息整合
        //min       左树最小、右树最小、X的值三者中最小
        int min=Math.min(X.value,Math.min(lData.min, rData.min));
        //max
        int max=Math.max(X.value,Math.max(lData.max, rData.max));
        //情况1和2
        int maxBSTSize=Math.max(lData.maxBSTSize, rData.maxBSTSize);
        Node maxBSTHead= lData.maxBSTSize> rData.maxBSTSize? lData.maxBSTHead : rData.maxBSTHead;

        //情况3
        if(X.left==lData.maxBSTHead && X.right== rData.maxBSTHead
            && X.value> lData.max && X.value< rData.min){
            maxBSTSize= lData.maxBSTSize+ rData.maxBSTSize+1;
            maxBSTHead=X;
        }

        //信息全部收集完毕，返回
        return new ReturnType(maxBSTHead,maxBSTSi***,max);
    }


    /*dp流程：先遍历左子树收集信息，然后遍历右子树收集信息，最后在头节点做信息整合。
    因为是递归函数，所以对所有子树要求都一样，都返回ReturnType的实例
    后序遍历：时间复杂度O(N),空间复杂度O(h),h为树的深度
    * */
    public static Node getMaxBST(Node head){
        return process(head).maxBSTHead;
    }

    public static int getMaxBSTSize(Node head){
        return process(head).maxBSTSize;
    }



    public static void main(String[] args) {
        //第一行
        Scanner in=new Scanner(System.in);
        String[] input= in.nextLine().split(" ");
        int n= Integer.parseInt(input[0]);
        Node root=new Node(Integer.parseInt(input[1]));

        //构建树
        HashSet<Node> set= new HashSet<Node>();
        set.add(root);
        //遍历读取
        for (int i = 0; i < n; i++) {
            String[]nodes=in.nextLine().split(" ");
            int fatherValue=Integer.parseInt(nodes[0]);
            int leftValue=Integer.parseInt(nodes[1]);
            int rightValue=Integer.parseInt(nodes[2]);
            //遍历添加
            for (Node e:set){
                //1、比较节点
                if(e.value==fatherValue){
                    //2、建立左右节点
                    Node left= leftValue==0?null:new Node(leftValue);
                    Node right= rightValue==0?null:new Node(rightValue);
                    e.left=left;
                    e.right=right;
                    //3、左右入set
                    if(leftValue!=0){
                        set.add(left);
                    }
                    if(rightValue!=0){
                        set.add(right);
                    }
                    //4、remove
                    set.remove(e);
                    break;
                }
            }

        }

        int result= getMaxBSTSize(root);
        System.out.println(result);

    }