多子节点树中查找目标节点路径的方法问询

问题背景 #

我们定义了如下Node类：

Node(name: String, children: List<Node>?)

并构建了一棵节点树：

var node6 = Node("6", null)
var node5 = Node("5", null)
var node4 = Node("4", null)
var node3 = Node("3", listOf(node5, node6))
var node2 = Node("2", null)
var node1 = Node("1", listOf(node2, node3, node4))

在仅能访问根节点node1的情况下，需要找到目标节点node6的存储路径。

解决方案 #

通过递归遍历+栈记录路径的方式实现，代码如下：

fun recursiveCheck(
    nodeA: Node,
    nodePath: Stack<Node>,
    nodeToFind: String
) : Boolean {
    // 将当前节点入栈
    nodePath.push(nodeA)

    // 检查当前节点是否为目标节点
    if(nodeA.name == nodeToFind) {
        return true
    }

    // 如果当前节点有子节点，递归遍历所有子节点
    if(nodeA.children != null) {
        for(child in nodeA.children!!) {
            // 递归检查子节点，找到则直接返回true
            if(recursiveCheck(child, nodePath, nodeToFind)) return true
        }
    }

    // 当前节点及其子节点中未找到目标，将当前节点出栈
    nodePath.pop()
    return false
}

代码逻辑说明 #

• 路径记录：用栈nodePath实时记录遍历节点的路径，每进入一个节点就将其入栈。
• 目标判断：遍历节点时先检查是否为目标节点，若是则返回true，此时栈中即为根节点到目标节点的完整路径。
• 递归遍历：若当前节点有子节点，逐个递归检查子节点，一旦子节点递归返回true，说明找到目标，直接向上返回true。
• 回溯处理：若当前节点的所有子节点遍历完仍未找到目标，将当前节点出栈（回溯），返回false，继续上层节点的其他子节点遍历。

使用示例 #

调用时初始化空栈，传入根节点node1和目标节点名称"6"，返回true时栈中元素即为路径：

val path = Stack<Node>()
if(recursiveCheck(node1, path, "6")) {
    path.forEach { println(it.name) }
}

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