一道前端算法题, 想了要好久没想出来如何写 . 请大神指导一下

递归考虑下

递归，把当前的路径传下去就行了。

To iterate is human, to recurse divine.

递归我试了, 往下传路径的时候似乎有问题, 各位答主最好能给个可以运行的代码

用栈吖，回溯法

function findPhone(name, node, path ) {
const newPath = path + '/' + node.name;
if (node.name != name) {
if (node.childs) {
for (let item of node.childs) {
const result = findPhone(name, item, newPath)
if(result) {
return result;
}
}
return false;
} else {
return false;
}
} else {
return newPath;
}
}

findPhone('iPhone X', data[0], '');

实现上可能复杂了点，但是我感觉没必要用栈就是。还得维护状态，直接用基础类型参数连状态都不用管

function getPathByName(data,objName){
var cOnf= {};
function getConf(_data,_path){
for(var i in _data){
var __path = _path? _path + "/"+_data[i].name:_data[i].name;
conf[_data[i].name] = __path;
if(_data[i].childs){
getConf(_data[i].childs,__path);
}
}
}
getConf(data,"");
return conf[objName];
}
alert(getPathByName(data,"HUAWEI Mate 20 Pro"));

@wly19960911 首先感谢你的回答. 我感觉这个 result 很关键. 这个我就没想到. 我当时就没想到如何在递归中摒弃不需要的路径

function getPathByName(data,objName){
var path="";
function getConf(_data,_path){
for(var i in _data){
var __path = _path? _path + "/"+_data[i].name:_data[i].name;
if(objName==_data[i].name){
path = __path;
return;
}
if(_data[i].childs){
getConf(_data[i].childs,__path);
}
}
}
getConf(data,"");
return path;
}
alert(getPathByName(data,"HUAWEI Mate 20 Pro"));

@noviceiOS 谢谢, 很棒的回答, 我需要慢慢看下

为什么不直接预处理一下 { name: a, childs: [b,c,d] } 转成 { b: 'a/b', ... }

path = ""
function query(tree,name) {
path += "/" + tree.name
if (tree.name == name) {
console.log(path)
return
}
var childs = tree.childs
if (childs != undefined) {
for ( var i = 0; i <childs.length; i++){
query(childs[i],name)
}
}
path= path.substring(0,path.lastIndexOf('/'))
}


不太擅长 js

query(data[0],"name")

function phoneSearch(targetName, data, path){
data.map(function (item) {
let currentPath = path + '/' + item.name;
if(item.name === targetName){
return currentPath;
}else if (item.children) {
phoneSearch(targetName, item.children, currentPath);
}
})
}

phoneSearch('HUAWEI Mate 20', data, '');

先 preprocess 把结构 flatten，每次询问时进行路径压缩。

但是这个数据结构品位很差，因为 child 的复数是一 children。

```
const data = [
{
name: "手机",
childs: [
{
name: "iPhone",
childs: [
{ name: "iPhone X" },
{ name: "iPhone XR" },
{ name: "iPhone XS" }
]
},
{
name: "HUAWEI",
childs: [
{ name: "HUAWEI Mate 20" },
{ name: "HUAWEI Mate 20 X" },
{ name: "HUAWEI Mate 20 Pro" }
]
}
]
}
];

const query = (items, arg) =>
items.map(item => {
// 如果名字相同
if (item.name === arg) return item.name;

// 如果没有子集
if (!item.childs) return null;

// 遍历查找子级，并过滤不相干内容
const childrenResult = query(item.childs, arg).filter(item => !!item);

// 找到了内容，携带当前名字一同返回上一级
if (childrenResult.length) return `${item.name} => ${childrenResult[0]}`;

// 子级也未找到
return null;
}).filter(item => !!item);

query(data, 'HUAWEI Mate 20 Pro')

// ["手机 => HUAWEI => HUAWEI Mate 20 Pro"]

```

没做任何优化，还是挺好懂得吧

这不就是最纯粹的递归吗？怎么看楼上一堆还传 path 进去的，还有写 2 个函数的？这就是最简单的递归模式啊

function getPath(data, name ) {
for (var i = 0; i < data.length; i++) {
if (data[i].name == name)
return "/" + name;
else if (data[i].childs) {
var next = getPath(data[i].childs, name);
if (next)
return "/" + data[i].name + next;
}
}
return "";
}
getPath(data, "HUAWEI Mate 20 X");

有人考虑过把结构压扁，然后用字符串操作吗

function getPhone(node, phone, path) {
path = path + '/' + node.name;
if (node.name === phone) {
return path;
}
if (node.childs) {
for (const child of node.childs) {
const res = getPhone(child, phone, path);
if (res) { return res; }
}
}
}
console.log(getPhone(data[0], 'HUAWEI Mate 20 Pro', ''));

function getPhonePath(data = [], name, prefix = []) {
for (let i = 0, len = data.length; i < len; i++) {
let tmp = data[i];
if (prefix.isFind) return prefix;
prefix.push(tmp.name);
if (tmp.name === name && (prefix.isFind = true)) return prefix;
if (tmp.childs) getPhonePath(tmp.childs, name, prefix)
!prefix.isFind && prefix.pop();
}
return [...prefix];
}

console.log(getPhonePath(data, "HUAWEI Mate 20 X"));

加个标志，可以少一层循环。

@lyshine 竟然从这跑去 sf 了

递归就完了
```
function name2path(list, name, path) {
return list.reduce((prev, item) => {
if (item.name === name) {
return path + '/' + item.name
}
else {
if (item.children) {
return name2path(item.children, name, path + '/' + item.name) || prev
}
return prev
}
}, path)
}
```

@redbuck

错了 reduce 第二个参数应该是''

function name2path(list, name, path) {
return list.reduce((prev, item) => {
// ...
}, '')
}

@nikandaoleshenme 这都被你发现了. 哈哈哈今天刚注册的

@zqx 你可以看 6 楼的, 他的实现就是扁平了结构

@zqx 错了 , 是 8 楼的实现

python 写的
def iter_names(a, prefix=''):
for i in a:
if 'childs' in i:
ite(i['childs'], prefix=prefix + i['name'] + '/')
else:
print prefix + i['name']

function retrievePath(phoneName,obj) {
for (let i in obj) {
if (obj[i]['childs']) {
let returnStr = retrievePath(phoneName,obj[i]['childs'])
if (returnStr !== '')
return '/' + obj[i]['name'] + returnStr
}else {
if (phOneName=== obj[i]['name']) {
return '/' + obj[i]['name']
}
}
}
}

function findPath(data, target) {
let path = ""; // 用于存储路径

function traverse(node, currentPath) {
if (node.name === target) {
path = currentPath; // 找到目标节点时更新路径
return;
}

if (node.childs) {
for (let i = 0; i < node.childs.length; i++) {
const child = node.childs[i];
const newPath = currentPath ? `${currentPath} / ${child.name}` : child.name;
traverse(child, newPath); // 递归遍历子节点
}
}
}

traverse(data, "");

return path;
}

// 测试
var data = [
{
name: "手机",
childs: [
{
name: "iPhone",
childs: [
{ name: "iPhone X" },
{ name: "iPhone XR" },
{ name: "iPhone XS" },
],
},
{
name: "HUAWEI",
childs: [
{ name: "HUAWEI Mate 20" },
{ name: "HUAWEI Mate 20 X" },
{ name: "HUAWEI Mate 20 Pro" },
],
},
],
},
];

console.log(findPath(data[0], "HUAWEI Mate 20")); // 输出 "手机 / HUAWEI / HUAWEI Mate 20"
//findPath 函数接受两个参数：data 是树的根节点，target 是要查找的目标节点的名称。函数通过递归遍历树的节点，每次遍历时更新当前路径，并检查当前节点是否为目标节点，如果是则将路径存储到 path 变量中。最终返回得到的路径。这个可以适用于多层的数据结构，因为它通过递归方式遍历树的每个节点，不论树的深度有多大，都能正确地找到路径。