PAT 甲级 1004 Counting Leaves (30 分)（Java）

• PAT 甲级 1004 Counting Leaves (30 分)（Java）
• • 题目
  • 题意解读
  • 解题思路
  • 解法
  • • 解法一
    • 解法二

题目链接

这题就是给出一棵树，然后给出节点数，非叶子节点给出相应的孩子节点id，然后问每一层叶子节点的个数；

首先，通过一些数据结构保存这棵树以及节点之间的父子关系，我这里采用了static List d = new ArrayList<>(101);（当然这里使用HashMap也是良法），相当于二维数组，第一维表示节点数，这里开到最大的节点数，第二维表示当前节点的孩子节点id，采用动态长度，有多少个元素添加多少；接下来，就是通过遍历来判断每一层的叶子节点的个数，因为这里是多叉树，所以可以采用前序遍历，也可以认为是深搜，也可以层序遍历，也就是广搜；

采用深搜的方式

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static List> d = new ArrayList<>(101); // 相当于可变长二维数组
    static int[] res = new int[101]; // 每一层非叶子节点个数
    static int max = -1; // 最大的层数

    public static void dfs(int index, int depth){
        if(d.get(index).size() == 0){
            res[depth]++;
            max = Math.max(max, depth);
            return;
        }
        for(int i=0; i l = new ArrayList<>();
            d.add(l);
        }
        int m = sc.nextInt();
        for(int i=0; i 
解法二 
采用广搜的方式
 
import java.util.*;

public class Main {
    static List> d = new ArrayList<>(101); // 相当于可变长二维数组
    static int[] res = new int[101]; // 每一层非叶子节点个数
    static int level = 0; // 当前的层数
    static Deque deque = new linkedList<>();

    public static void bfs(){
        while(!deque.isEmpty()){
            int size = deque.size();
            for (int i = size-1; i >= 0; --i) {
                int cur = deque.pollFirst();
                if(d.get(cur).size() == 0){
                    res[level]++;
                }else {
                    for (int j = 0; j < d.get(cur).size(); j++) {
                        deque.addLast(d.get(cur).get(j));
                    }
                }
            }
            level++;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if(n == 0){
            return;
        }
        // 相当于给二维数组的第二维做初始化
        for(int i=0; i<101; ++i){
            List l = new ArrayList<>();
            d.add(l);
        }
        int m = sc.nextInt();
        for(int i=0; i