最近疫情在家办公，足不出户，做做 PAT 的题。奉上【PAT甲级】JS 解题分析————第三篇。（1003 Emergency 暂时还不会，先跳过，哈哈）
原题
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 0<N<100, the number of nodes in a tree, and M (<N), the number of non-leaf nodes. Then M lines follow, each in the format:
ID K ID[1] ID[2] ... ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01.
The input ends with N being 0. That case must NOT be processed.
Output Specification:
For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.
The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output 0 1 in a line.
Sample Input:
2 1
01 1 02
Sample Output:
0 1
原题翻译
一个家族的等级通常通过家谱的形式呈现。你的任务就是找出那些没有孩子的家族成员。
输入说明：
- 输入的第一行，包含两个数字 N 和 M，N 是节点总数
0<N<100, M 非叶子节点的数量<N。 - 第一行后面有 M行，每行的格式为
ID K ID[1] ID[2] ... ID[K]，其中 ID 是两位数字代表非叶子节点，K 是该节点的子节点数量，后面是子节点的 IDS。 - 为了简单，根节点 ID 定为 01。
- 如果输入 N 的值为 0， 不作处理。
输出说明：
- 对每个测试用例，你需要输出每个层级叶子节点的数量，以空格分割在一行输出。
- 举个简单的例子：树有2个节点，01 是根节点，02是它唯一的子节点。那么根节点这一级叶子节点数量为0，下一级叶子阶段数为1，输出
0 1。
简单来说，就是找出每层的叶子节点数。
解题
思路：
- 思路一：深度优先遍历DFS，使用数组存储子节点，从上往下递归，到叶子节点结束，记录每层的叶子节点数量。
- 思路二：广度优先遍历BFS，从根节点开始入队，队首节点出队，其子节点入队，统计叶子节点数量。
注意事项：
- 可能会碰到 1004 Counting Leaves 测试点4 结果为 答案错误 或 非零输入，原因是后面 M行的输入可能换行，在做字符串分割时需要用
string.split(/[\s\n]/)。
测试用例：
- input: “1”; output “1”
- input: “2 1”, “01 1 02”; output: “0 1”
- input: “3 2”, “01 1 02”, “02 1 03”; output: “0 0 1”
- input: “15 9”, “01 2 02 03”, “02 3 04 05\n06”, “03 2 07 08”, “05 2 09 10”, “07 1 12”, “08 1 13”, “09 1 11”, “11 1 14”, “13 1 15”; output: “0 0 2 2 1 1”
代码：
const readline = require('readline');
rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
// 多行输入（行数视参数而定）
let K = -1;
const inputs = [];
rl.on('line', function(data) {
// 读取第一行的数据，获取 K-总行数的值
if(K < 0) {
const [N, M] = data.trim().split(' ');
K = M ? M * 1 + 1 : 1;
}
// 获取输入
inputs.push(data.trim());
if (K == inputs.length) {
// 处理
const ret = deal(inputs);
if(ret) {
// 输出结果
console.log(ret);
}
// 清0
inputs.length = 0;
}
});
深度优先遍历 DFS
/**
* 处理逻辑-dfs
* @param {array} 入参集合
* @returns {string} 返回值
*/
function deal(arg) {
const [firstLine, ...restLines] = arg;
const [N, M] = firstLine.split(" ").map((item) => item * 1);
// N 为 0 或空，直接返回
if (!N) return;
// 最大深度
let maxDepth = -1;
// 记录每层的叶子节点数量
const countList = new Array(N + 1).fill(0);
// 记录 M 行的子节点
const leavesList = [];
// 处理第一行后面的 M 行
for (let i = 0; i < M; i++) {
// ID K ID[1] ID[2] ... ID[K]
const line = restLines[i].split(/[\s\n]/).map((item) => item * 1);
const id = line[0];
leavesList[id] = line.slice(2);
}
/**
* 深度优先遍历
* @param {number} index 序号
* @param {number} depth 深度
*/
function dfs(index, depth) {
// 终止条件：叶子节点
if (!leavesList[index]) {
countList[depth]++;
maxDepth = Math.max(maxDepth, depth);
return;
}
// 递归处理下一层的子节点
for (let i = 0; i < leavesList[index].length; i++) {
dfs(leavesList[index][i], depth + 1);
}
}
dfs(1, 0);
return countList.slice(0, maxDepth + 1).join(" ");
}
广度优先遍历 BFS
DFS 向下遍历，便于统计层次。与 DFS 不同，BFS 需要一个额外的数组记录每个节点所在层次。
/**
* 处理逻辑-bfs
* @param {array} 入参集合
* @returns {string} 返回值
*/
function deal(arg) {
const [firstLine, ...restLines] = arg;
const [N, M] = firstLine.split(" ").map((item) => item * 1);
// N 为 0 或空，直接返回
if (!N) return;
// 最大深度
let maxDepth = -1;
// 记录每层的叶子节点数量
const countList = new Array(N + 1).fill(0);
// 记录每个节点所在层级
const depthList = new Array(N + 1).fill(-1);
// 记录 M 行的子节点
const leavesList = [];
// 处理第一行后面的 M 行
for (let i = 0; i < M; i++) {
// ID K ID[1] ID[2] ... ID[K]
const line = restLines[i].split(/[\s\n]/).map((item) => item * 1);
const id = line[0];
leavesList[id] = line.slice(2);
}
// 广度优先遍历
function bfs() {
// 根节点
const q = [1];
depthList[1] = 0;
while(q.length) {
// 获取队首节点
const index = q.shift();
const nodes = leavesList[index];
// 更新最大层级
maxDepth = Math.max(depthList[index], maxDepth);
// 统计叶子节点
if(!nodes) {
countList[depthList[index]] ++;
continue;
}
// 对队首节点的所有子节点遍历，入队，记录层级
for(let i = 0; i < nodes.length; i++) {
q.push(nodes[i]);
depthList[nodes[i]] = depthList[index] + 1;
}
}
}
bfs();
return countList.slice(0, maxDepth + 1).join(" ");
}
PAT 考试练习，JavaScript(node) 在线答题，需使用 node 的 readline 逐行读取 input, 通过 console.log 打印 output。上述代码给出了多行输入（具体行数视输入而定）的处理方式。