通过指定参数遍历嵌套列表到 return 内部列表

Question

目标是 return 对象的内部列表，其中包含来自数据列表的给定参数。将在其上找到此对象的图层可能会有所不同。

对象的伪代码是

class Object {
   var id: Int
   var innerObjects: ArrayList<Object>
}

如果 innerObjects param 为 null 那么我们到达了叶节点。

我们得到 ArrayList<Object> 这是我们正在搜索的数据和 id。我们搜索的对象可以在列表的任何级别。

我现在拥有的是这段代码，但它只检查列表的 2 级。请提出一个适用于列表中任意数量级别的解决方案。可能与递归。

private fun getObject(data: ArrayList<Object>, id: Int): ArrayList<Object> {
        var result = ArrayList<Object>()
        for (i in 0 until data.size) {
            if (data[i].id == id) {
                result = data[i].innerObjects
            } else {
                for (j in 0 until data[i].innerObjects.size) {
                    if (data[i].innerObjects[j].id == id) {
                        result = data[i].innerObjects[j].innerObjects
                    }
                }
            }
        }
        return result
    }

顺便说一下，代码是在 Kotlin 中，但请随意提出解决方案 Kotlin 或 Java.

Answer 1

因此，在这种情况下使用基本递归将解决此问题，但要注意，因为这种搜索可以快速生成文字 WhosebugExceptions。

fun getInnerObjectsById(nodes: ArrayList<Object>, id: Int) : ArrayList<Object>? {
    nodes.forEach{
        val ans = solve(it, id)
        if (ans != null) return ans
    }
    return null
}

fun getInnerObjectsById(obj: Object?, id: Int): ArrayList<Object>? {
    if (obj?.id == null || obj.innerObjects == null) return null
    if (obj.id == id) return obj.innerObjects
    return obj.innerObjects?.mapNotNull {
        solve(it, id)
    }?.firstOrNull()
}

这是一个更复杂但势在必行的搜索。

fun getInnerObjectsById(data: ArrayList<Object>, id: Int): ArrayList<Object>? {
    var activeList: List<Object> = data
    while (true) {
        val match = activeList.firstOrNull { it.id == id }
        if (match != null) return match.innerObjects
        activeList = activeList.flatMap { it.innerObjects ?: emptyList<Object>() }

        if (!activeList.isNotEmpty())
            return null
    }
}

Answer 2

我已经为解决方案编写了 java 代码：

ArrayList<TreeNode> solve(TreeNode treeNode, int id) {
    if(treeNode == null) return null;
    if(treeNode.id == id) return treeNode.nodes;
    if(treeNode.nodes == null) return null;
    ArrayList<TreeNode> ans = null, temp = null;
    for(TreeNode t: treeNode.nodes) {
        temp = solve(t, id);
        if(temp != null) ans = temp;
    }
    return ans;
}

Ideone 演示：https://ideone.com/cMmAqD

Answer 3

我在Kotlin中为我的案例申请的解决方案，供有兴趣的人使用！

private fun getObjectById(item: Object, id: Int): ArrayList<Object>? {
    if (item.id == id) return item.innerObjects
    for (child in item.innerObjects) {
        val temp = getObjectById(child, id)
        if (temp!!.isNotEmpty()) return temp
    }
    return ArrayList()
}

fun combineLists(data: ArrayList<Object>?, id: Int) {
    for (j in 0 until data.size) {
         getObjectById(data[j], id)?.let {
            result.clear()
            result.addAll(it)
         }
    }
}

通过指定参数遍历嵌套列表到 return 内部列表

Iterate through nested List to return inner List by specified param

java

algorithm

kotlin

depth-first-search

breadth-first-search