如何从树形结构中准确提取所有叶子节点和父节点 ID

今天早睡

发布时间：2026-08-25| 94人浏览过

原创

前言

在树形结构处理中，最容易被误判的不是树有没有生成出来，而是深层节点的统计结果有没有完整带回。本文用一段 PHP 递归示例拆开说明：为什么 `leaf_ids` 会丢、`parent_ids` 会不全，以及怎样通过合并子树返回值，把叶子节点和父节点 ID 一次性收集准确。

在菜单、组织架构、分类目录这类无限层级结构里，开发者往往先关注树是否能正确生成，却容易忽略“附带统计信息”是否也被完整带出来。本文围绕一个常见递归漏洞展开：为什么树构建看似正常，但 leaf_ids 和 parent_ids 却不对；以及应当怎样改，才能让每一层子树产生的结果都被准确合并到最终输出中。

问题出在哪里：树构建成功，不代表叶子和父节点统计正确

这类问题通常发生在递归构建树的过程中。代码会递归调用 makeTree() 生成子节点结构，但调用返回后，只取了其中的 tree 字段挂到当前节点的 children 上，却没有把子树内部已经算出的 leaf_ids 和 parent_ids 一并合并回来。

结果就是：当前层能识别出的父节点和叶子节点会被记录，但更深层递归里产生的 ID 信息会被直接丢失。这样一来，最终输出的树看起来没问题，元数据却严重不完整，典型表现就是 leaf_ids 为空，或者 parent_ids 缺少深层节点。

这也是递归处理树结构时最容易被忽视的一点：树形结果是逐层挂接的，统计结果也必须逐层回传并合并。

修复思路：递归返回后，把子树结果向上合并

修复方法本身并不复杂，关键在于保持递归返回值的完整性。每次调用 makeTree() 构建某个节点的子树后，除了把 tree 赋给 children，还要把子树返回的 leaf_ids 和 parent_ids 合并到当前层级的结果数组中。

展示递归构建树时，子树返回 tree、leaf_ids、parent_ids 并向父层合并的暖色专栏配图 — **递归返回值要完整回传**子树返回值不能只接 tree，叶子与父节点统计也要一起向上合并。

同时，当前节点如果存在子节点，它本身就应被归类为父节点；如果没有子节点，它才属于叶子节点。下面这份实现完整保留了这个逻辑：

function build(array $array): array
{
if (empty($array)) {
return [
'leaf_ids' => [],
'parent_ids' => [],
'tree' => [],
];
}

// 按 parent_id 分组（NULL/0 视为根）
$groupByParent = [];
foreach ($array as $item) {
$parentId = $item['parent_id'] ?? 0;
$groupByParent[$parentId][] = $item;
}

return makeTree($groupByParent, $groupByParent[0] ?? []);
}

function makeTree(array &$parentList, array $items): array
{
$tree = [];
$leafIds = [];
$parentIds = [];

foreach ($items as $item) {
$hasChildren = isset($parentList[$item['id']]) && !empty($parentList[$item['id']]);

if ($hasChildren) {
// 递归构建子树，并合并其 leaf_ids 和 parent_ids
$subResult = makeTree($parentList, $parentList[$item['id']]);
$item['children'] = $subResult['tree'];
$leafIds = array_merge($leafIds, $subResult['leaf_ids']);
$parentIds = array_merge($parentIds, $subResult['parent_ids']);
$parentIds[] = $item['id']; // 当前节点是父节点
} else {
$leafIds[] = $item['id']; // 当前节点是叶子节点
}

$tree[] = $item;
}

return [
'tree' => $tree,
'leaf_ids' => $leafIds,
'parent_ids' => $parentIds,
];
}

这段代码的核心变化只有一个：子树不仅返回结构，还返回统计结果；父层不能只接树，不接统计。只要这一点处理到位，无论树有多少层，叶子节点和父节点的 ID 都能跟着递归完整回流到最终结果中。

用示例验证：哪些节点应该进 leaf_ids，哪些应该进 parent_ids

看一组输入数据会更直观。这个例子里，节点 1 和 2 位于根层，节点 3、4 挂在 1 下，节点 5 挂在 2 下，而节点 6 又挂在 5 下，因此它是一层更深的叶子节点。

展示示例树中 1、2、5 为父节点，3、4、6 为叶子节点的暖色专栏配图 — **示例数据的归类结果**用一组 6 个节点的树结构，可以直观看出 leaf_ids 和 parent_ids。

$array = [
['id' => 1, 'parent_id' => null, 'value' => 'Hi'],
['id' => 2, 'parent_id' => null, 'value' => 'Bye'],
['id' => 3, 'parent_id' => 1, 'value' => 'Hey'],
['id' => 4, 'parent_id' => 1, 'value' => 'Hello'],
['id' => 5, 'parent_id' => 2, 'value' => 'Cya'],
['id' => 6, 'parent_id' => 5, 'value' => 'Byebye'],
];

这组数据下，预期结果应当是：

"leaf_ids": [3, 4, 6]：节点 3 和 4 没有子节点，节点 6 虽然位于更深层，但同样没有子节点，因此也必须被识别为叶子节点；
"parent_ids": [1, 2, 5]：节点 1 拥有子节点 3、4，节点 2 拥有子节点 5，而节点 5 又拥有子节点 6，所以三者都属于父节点。

如果你的实现最终没拿到节点 6，或者漏掉节点 5，通常就能直接判断出：递归调用后的返回值没有被完整合并。这个例子也说明了一点，树结构问题不能只看第一层输出是否对，必须拿包含多层嵌套的数据做验证，才能暴露统计链路是否断裂。