Swift中如何实现递归获取Tag节点的完整父路径？

定义与需求 #

Tag类定义 #

final class Tag {
  let title: String
  let tags: [Tag] // 标签可以包含任意数量的子标签
}

let myTags = [Tag]() // 已填充数据

需求说明 #

给定一个Tag实例，需要按顺序获取它的所有父节点组成的完整路径。例如在模拟数据中查找标签"A122"，应返回父节点数组["Flight", "A1", "A12"]。

尝试的错误实现 #

我尝试了递归实现但运行不正确，当前代码如下：

func searchPath(for tag: Tag, in data: [Tag], path: [Tag]) -> [Tag]? {
    for child in data {
        print(child.title)
        if child.tags.isEmpty && child == tag {
            return path
        } else if !child.tags.isEmpty {
            return searchPath(for: tag, in: child.tags, path: path + [child])
        } else {
        }
    }
    return []
}

问题分析 #

当前代码存在几个关键问题：

• 仅判断叶子节点（child.tags.isEmpty）是否为目标，若目标节点有子节点则无法匹配
• 遍历子节点时，一遇到非空标签就直接递归返回，没有遍历当前层级的其他节点，可能错过正确路径
• 未找到目标时返回空数组[]，而非nil，无法区分"没找到"和"无父节点"的情况

模拟数据示例 #

private let mock: [Tag] = {
    [
        .init(title: "Car", tags: [
            .init(title: "Porsche", tags: []),
            .init(title: "BMW", tags: [])
        ]),
        .init(title: "Flight", tags: [
            .init(title: "A1", tags: [
                .init(title: "A11", tags: []),
                .init(title: "A12", tags: [
                    .init(title: "A121", tags: []),
                    .init(title: "A122", tags: [])
                ])
            ]),
            .init(title: "A2", tags: [])
        ])
    ]
}()

正确的递归实现 #

func searchPath(for targetTag: Tag, in tags: [Tag], currentPath: [Tag] = []) -> [Tag]? {
    for tag in tags {
        // 检查当前节点是否为目标，若是则返回当前路径（父节点集合）
        if tag === targetTag {
            return currentPath
        }
        // 递归遍历子节点，将当前节点加入路径
        if let foundPath = searchPath(for: targetTag, in: tag.tags, currentPath: currentPath + [tag]) {
            return foundPath
        }
    }
    // 未找到目标节点，返回nil
    return nil
}

调用示例 #

// 假设已获取mock中的A122实例
if let a122 = mock[1].tags[0].tags[1].tags[1],
   let path = searchPath(for: a122, in: mock) {
    let pathTitles = path.map { $0.title }
    print(pathTitles) // 输出: ["Flight", "A1", "A12"]
}

代码说明 #

• 引用判断：使用===判断两个Tag实例是否为同一引用（因Tag是class类型）
• 递归逻辑：遍历每个节点时先检查是否为目标；若不是则递归遍历其子节点，并将当前节点加入路径
• 路径传递：递归时传递当前路径的副本，避免修改原数组
• 无匹配处理：未找到目标时返回nil，明确区分"未找到"和"无父节点"的场景

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