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

题目

左孩子右兄弟 - 蓝桥云课

---

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

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

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

给定一棵包含 $N$ 个结点的多叉树，结点从 $1$ 至 $N$ 编号，其中 $1$ 号结点是根，每个结点的父结点的编号比自己的编号小。

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

注：只有根结点这一个结点的树高度为 $0$。

输入描述

输入的第一行包含一个整数 $N$。 以下 $N −1$ 行，每行包含一个整数，依次表示 $2$ 至 $N$ 号结点的父结点编号。

输出描述

输出一个整数表示答案。

输入输出样例

示例 1

输入

5
1
1
1
2

输出

4

评测用例规模与约定

对于 $30\%$ 的评测用例，$1 \leq N \leq 20$；

对于所有评测用例，$1 \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));
    }
}