侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【DFS】左孩子右兄弟【蓝桥杯】

GabrielxD
2022-12-28 / 0 评论 / 0 点赞 / 15 阅读 / 589 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2023-01-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

左孩子右兄弟 - 蓝桥云课


对于一棵多叉树,我们可以通过 “左孩子右兄弟” 表示法,将其转化成一棵二叉树。

如果我们认为每个结点的子结点是无序的,那么得到的二叉树可能不唯一。

换句话说,每个结点可以选任意子结点作为左孩子,并按任意顺序连接右兄弟。

给定一棵包含 NN 个结点的多叉树,结点从 11NN 编号,其中 11 号结点是根,每个结点的父结点的编号比自己的编号小。

请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树,高度最高是多少。

注:只有根结点这一个结点的树高度为 00

输入描述

输入的第一行包含一个整数 NN。 以下 N1N −1 行,每行包含一个整数,依次表示 22NN 号结点的父结点编号。

输出描述

输出一个整数表示答案。

输入输出样例

示例 1

输入

5
1
1
1
2

输出

4

评测用例规模与约定

对于 30%30\% 的评测用例,1N201 \leq N \leq 20

对于所有评测用例,1N1000001 \leq N \leq 100000

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

解题

方法一:DFS

思路

以某节点为根节点的子树的最高高度为 = 所有子节点中经过左孩子右兄弟转换后的最高高度 + 除了子节点以外的所有子节点数量(children.size() - 1) + 根节点(1)。

按照以上规则递归深搜即可。

代码

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

public class Main {
    static Map<Integer, List<Integer>> mp = new HashMap<>();

    static int dfs(int node) {
        if (!mp.containsKey(node)) return 0;
        List<Integer> children = mp.get(node);
        int h = 0;
        for (int child : children) h = Math.max(h, dfs(child));
        return h + children.size();
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        for (int i = 2; i <= n; ++i) {
            in.nextToken();
            int p = (int) in.nval;
            mp.putIfAbsent(p, new ArrayList<>());
            mp.get(p).add(i);
        }
        System.out.println(dfs(1));
    }
}
0

评论区