JS 树(数组存储)进行递归遍历获取路径
实现功能:
通过叶子节点 id ,寻找包含该叶子节点的整条路径。(树的数据以数组形式保存)
直接上代码:
const getPathByKey = (curKey, data) => {
let result = []; // 记录路径结果
let traverse = (curKey, path, data) => {
if (data.length === 0) {
return;
}
for (let item of data) {
path.push(item);
if (item.id === curKey) {
result = JSON.parse(JSON.stringify(path));
return;
}
const children = Array.isArray(item.children) ? item.children : [];
traverse(curKey, path, children); // 遍历
path.pop(); // 回溯
}
}
traverse(curKey, [], data);
return result;
}
数据示例:
const data = [
{
code: "090",
id: "090",
children: [
{
code: "0901",
id: "0901",
children: [
{
code: "090101",
id: "090101",
},
{
code: "090202",
id: "090202",
},
]
},
{
code: "0902",
id: "0902",
},
]
},
{
code: "091",
id: "091",
children: [],
},
{
code: "092",
id: "092",
children: [
{
code: "0921",
id: "0921",
},
{
code: "0922",
id: "0922",
children: [
{
code: "092201",
id: "092201",
children: [
{
code: "09220101",
id: "09220101",
},
]
},
]
},
]
},
];
// ...
getPathByKey('09220101', data);
结果展示
查找 id 为 09220101 的叶子节点 到根节点的路径, 遍历后结果路径 id 正好对应。
这是第一次实际运用回溯思想到实际的工作当中,之前虽然有练习到回溯与寻找路径的算法题,但根据实际情况应用还是和平时的算法题有区别,实际的算法实现和数据结构还要比这里展示的复杂一些,本方法是抽取了原算法的思想及简化后的数据结构,可以作为参考。