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

package com.wyj.ch3;

import java.util.HashSet;
import java.util.Scanner;

/**
 * @author： wyj
 * @describe：
 * @version：V01
 * @date： 2021/7/26- 21:46
 */
public class h3a8 {
    static class Node{
        int value;
        Node left;
        Node right;

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

    //
    public static int bstTopoSize(Node head){
        if(head==null){
            return 0;
        }
        int max=maxTopo(head,head);
        max=Math.max(bstTopoSize(head.left),max);
        max=Math.max(bstTopoSize(head.right),max);
        return max;
    }

    //搜索以h为头节点的最大拓扑结构
    public static int maxTopo(Node h, Node n){
        if(h!=null&& n!=null&& isBSTNode(h,n)){
            return maxTopo(h,n.left)+maxTopo(h,n.right)+1;
        }
        return 0;
    }

    // 判断node n是否在以h为头节点的搜索二叉树上
    public static boolean isBSTNode(Node h,Node n){
        if(h==null){
            return false;
        }
        if(h==n){
            return true;
        }
        return isBSTNode(h.value> n.value? h.left:h.right, n);
    }


    /*创建无ID的树
    in: 3 2
        2 1 3
        1 0 0
        3 0 0
    * */
    public static Node createTree(Scanner in, int n){
        int rootValue=in.nextInt();
        Node root=new Node(rootValue);
        HashSet<Node> set=new HashSet<Node>();
        set.add(root);

        //n行读取
        for (int i = 0; i < n; i++) {
            int fatherValue= in.nextInt();
            int leftValue=in.nextInt();
            int rightValue=in.nextInt();
            //遍历
            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、放入节点
                    if(leftValue!=0){
                        set.add(left);
                    }
                    if(rightValue!=0){
                        set.add(right);
                    }
                    //4、remove
                    set.remove(e);
                    break;
                }
            }

        }


        return root;
    }

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        Node root= createTree(in,n);
        int result= bstTopoSize(root);
        System.out.println(result);
    }

}