一维ID数组与多维分类树匹配：分支末节点提取需求求助

嘿，别担心，这个问题看起来绕，但理清逻辑后其实挺清晰的！我先帮你拆解需求，再给你修正代码的思路和实现。

需求拆解 #

你要做的核心是：

• 遍历一棵多维分类树（每个节点是Category对象，带Id、parentId、subcategories这类子节点属性）
• 给定一个一维ID数组，找出每个分支中属于这个数组的最靠下的节点（不一定是叶子节点，只要它下面的分支里没有属于目标数组的节点就行）
• 比如你举的例子：目标数组[1,5,11,12,4,8]，分类树分支1→5→11→12里最末符合条件的是12；分支6→8里最末的是8，最终结果就是[12,8]

核心思路 #

要高效解决这个问题，关键抓住两点：

1. 快速判断ID是否在目标数组：把目标ID数组转成哈希集合（PHP里用array_flip实现），这样判断ID存在的时间复杂度是O(1)，处理大规模树的时候效率会高很多。
2. 递归遍历+分支判断：遍历每个节点时，先递归检查它的子节点有没有符合条件的节点。如果子节点里有符合条件的，那结果来自子节点；如果子节点没有，而当前节点在目标数组里，那当前节点就是这个分支的答案。

代码修正与实现 #

第一步：重构递归函数 #

我帮你重新写了findCategoryLeaves函数，逻辑更清晰，能直接得到你要的结果：

private function findCategoryLeaves($categoryTree, $targetIds) {
    $result = [];

    foreach ($categoryTree as $node) {
        $nodeId = $node->getId();
        $hasValidChild = false;

        // 先递归遍历子节点，看看子节点里有没有符合条件的节点
        $subcategories = $node->getSubcategories();
        if (!empty($subcategories)) {
            $childResults = $this->findCategoryLeaves($subcategories, $targetIds);
            if (!empty($childResults)) {
                // 子节点有结果，合并到总结果里
                $result = array_merge($result, $childResults);
                $hasValidChild = true;
            }
        }

        // 如果当前节点在目标数组，且子节点没有符合条件的节点，就把它加入结果
        if (isset($targetIds[$nodeId]) && !$hasValidChild) {
            $result[] = $nodeId;
        }
    }

    return $result;
}

第二步：在主函数中调用 #

在你的buildRows函数里，替换原来的递归调用部分，先把目标ID数组转成哈希集合：

// 替换原来的$leaf[] = ... 这部分
$productCategories = $product->getCategories();
$targetIds = array_flip($productCategories); // 转成哈希集合，快速判断ID存在
$leaf = $this->findCategoryLeaves($this->categoryTree, $targetIds);
dump($leaf); // 这里就能得到你想要的结果啦

为什么你的原代码卡壳了？ #

你的原递归逻辑有点混乱：

• 没有区分“当前节点是否在目标数组”和“子节点是否有有效节点”的优先级，导致递归返回的结果没被正确处理
• 没有用哈希集合，每次判断ID是否存在都要遍历数组，效率低，大规模树会很慢
• 递归调用时参数传递错误，没有利用递归返回的结果

优化：迭代版本（避免栈溢出） #

如果你的分类树特别大，递归可能会触发PHP的栈溢出错误，这时候可以换成迭代的深度优先遍历：

private function findCategoryLeavesIterative($categoryTree, $targetIds) {
    $result = [];
    $stack = [];

    // 初始化栈，每个元素存[节点, 是否已处理子节点]
    foreach ($categoryTree as $node) {
        $stack[] = [$node, false];
    }

    while (!empty($stack)) {
        list($node, $processed) = array_pop($stack);
        $nodeId = $node->getId();
        $hasValidChild = false;

        if (!$processed) {
            // 第一次弹出，标记为已处理后重新压入，再压入子节点
            $stack[] = [$node, true];
            $subcategories = $node->getSubcategories();
            // 倒序压入子节点，保证遍历顺序和递归一致
            for ($i = count($subcategories) - 1; $i >= 0; $i--) {
                $stack[] = [$subcategories[$i], false];
            }
        } else {
            // 检查子节点是否有属于目标数组的节点
            foreach ($node->getSubcategories() as $child) {
                if (isset($targetIds[$child->getId()])) {
                    $hasValidChild = true;
                    break;
                }
            }

            // 当前节点符合条件且没有有效子节点，加入结果
            if (isset($targetIds[$nodeId]) && !$hasValidChild) {
                $result[] = $nodeId;
            }
        }
    }

    return $result;
}

这个版本用栈模拟递归，不会有栈溢出的问题，适合超大规模的分类树。

内容的提问来源于stack exchange，提问作者Jan Kocvik