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

import java.io.*;
import java.util.*;

public class Main {

    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    static class Info {
        boolean isBST;  // 当前树是否是二叉搜索树
        int size;       // 当前树的大小(节点数)
        int min;        // 当前树的最小值
        int max;        // 当前树的最大值
        Info(boolean isBST, int size, int min, int max) {
            this.isBST = isBST;
            this.size = size;
            this.min = min;
            this.max = max;
        }
    }

    static Map<Integer, TreeNode> nodeMap = new HashMap<>();
    static Map<Integer, int[]> childrenMap = new HashMap<>();
    static TreeNode root = null;
    static int maxNodes = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int rootVal = Integer.parseInt(firstLine[1]);

        // 初始化二叉树节点
        for (int i = 0; i < n; i++) {
            //建树时借助了hashMap
            String[] line = br.readLine().split(" ");
            int fa = Integer.parseInt(line[0]);
            int lch = Integer.parseInt(line[1]);
            int rch = Integer.parseInt(line[2]);

            if (!nodeMap.containsKey(fa)) {
                nodeMap.put(fa, new TreeNode(fa));
            }
            TreeNode node = nodeMap.get(fa);
            if (lch != 0) {
                if (!nodeMap.containsKey(lch)) {
                    nodeMap.put(lch, new TreeNode(lch));
                }
                node.left = nodeMap.get(lch);
            }
            if (rch != 0) {
                if (!nodeMap.containsKey(rch)) {
                    nodeMap.put(rch, new TreeNode(rch));
                }
                node.right = nodeMap.get(rch);
            }
        }

        root = nodeMap.get(rootVal);

        // 使用递归来计算最大搜索二叉子树
        findLargestBST(root);

        // 输出结果
        System.out.println(maxNodes);
    }

    // 后序遍历来处理每个节点,返回子树的信息
    public static Info findLargestBST(TreeNode node) {
        if (node == null) {
            return new Info(true, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }

        // 递归计算左右子树
        Info leftInfo = findLargestBST(node.left);
        Info rightInfo = findLargestBST(node.right);

        // 当前树是否是搜索二叉树的判断
        if (leftInfo.isBST && rightInfo.isBST && node.val > leftInfo.max &&
                node.val < rightInfo.min) {
            // 当前节点是搜索二叉树
            int size = leftInfo.size + rightInfo.size + 1;
            maxNodes = Math.max(maxNodes, size);  // 更新最大节点数
            return new Info(true, size, Math.min(node.val, leftInfo.min), Math.max(node.val,
                            rightInfo.max));
        } else {
            // 当前节点不是搜索二叉树
            return new Info(false, Math.max(leftInfo.size, rightInfo.size), 0, 0);
        }
    }
}

全部评论

相关推荐

06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
找个工作&nbsp;学历是要卡的&nbsp;要求是高的&nbsp;技能不足是真的&nbsp;实习经验是0的&nbsp;简历无处可写是事实的&nbsp;钱不好赚是真的&nbsp;想躺平又不敢躺&nbsp;也不甘心躺&nbsp;怕自己的灵感和才华被掩埋甚至从未被自己发现&nbsp;又质疑自己是否真正有才华
码农索隆:你现在啊,你心里都明白咋回事,但是你没办法改变现状,一想到未来,你又没有信心狠下心来在当下努力。 得走出这种状态,不能一直困在那里面,哪不行就去提升哪,你一动不动那指定改变不了未来,动起来,积少成多才能越来越好
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务