需求

存在如下數(shù)組，實現(xiàn)一個算法通過輸入?yún)^(qū)名，返回省->市->區(qū)格式的路徑，例如輸入西湖區(qū)，返回浙江省->杭州市->西湖區(qū)。

// 定義省市區(qū)的嵌套數(shù)組
const data = [{name: "浙江省",children: [{name: "杭州市",children: [{ name: "西湖區(qū)" },{ name: "上城區(qū)" },{ name: "下城區(qū)" }]},{name: "寧波市",children: [{ name: "海曙區(qū)" },{ name: "江東區(qū)" },{ name: "江北區(qū)" }]},{name: "溫州市",children: [{ name: "鹿城區(qū)" },{ name: "龍灣區(qū)" },{ name: "甌海區(qū)" }]}]},{name: "北京市",children: [{ name: "東城區(qū)", children: [] },{ name: "西城區(qū)", children: [] },{ name: "朝陽區(qū)", children: [] },{ name: "海淀區(qū)", children: [] }]},{name: "江蘇省",children: [{name: "南京市",children: [{ name: "玄武區(qū)" },{ name: "秦淮區(qū)" },{ name: "建鄴區(qū)" }]},{name: "蘇州市",children: [{ name: "姑蘇區(qū)" },{ name: "吳中區(qū)" },{ name: "相城區(qū)" }]},{name: "無錫市",children: [{ name: "梁溪區(qū)" },{ name: "濱湖區(qū)" },{ name: "新吳區(qū)" }]}]}
];

分析

數(shù)據(jù)是一個嵌套結(jié)構(gòu)，DFS 是一種合適的遍歷方法。它可以遞歸地深入到每個節(jié)點的子節(jié)點中進(jìn)行搜索。

但是需要考慮如果該節(jié)點下沒有查找到的情況，則需要將該節(jié)點從path中去掉，繼續(xù)遍歷下一個節(jié)點。

• 將當(dāng)前節(jié)點的名稱添加到路徑中。
• 如果當(dāng)前節(jié)點的名稱是目標(biāo)區(qū)名，返回 true 表示找到目標(biāo)，并保留路徑。
• 如果當(dāng)前節(jié)點有子節(jié)點，遞歸地對每個子節(jié)點調(diào)用 DFS。
• 如果在所有子節(jié)點中都沒有找到目標(biāo)，從路徑中移除當(dāng)前節(jié)點名稱，并返回 false。

代碼

// 定義DFS查找路徑的函數(shù)
function findPathDFS(node, target, path) {path.push(node.name);if (node.name === target) {return true;}if (node.children) {for (const child of node.children) {if (findPathDFS(child, target, path)) {return true;}}}path.pop();return false;
}function findPath(data, districtName) {const path = [];for (const province of data) {if (findPathDFS(province, districtName, path)) {return path;}}return null; // 未找到返回null
}// 測試查找路徑函數(shù)
const districtName = "西湖區(qū)";
const path = findPath(data, districtName);if (path) {console.log(`路徑: ${path.join(" -> ")}`);
} else {console.log("未找到該區(qū)");
}

結(jié)果：