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

[lyshine]

题目是:

给一个数据结构如下
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"},
            ]
        }
    ]
}

];

然后让封装一个函数, 根据名称得到其遍历的路径. 例如参数是  HUAWEI Mate 20. 那么函数返回 手机 / HUAWEI/HUAWEI Mate 20.  要求函数可以适用多层的数据结构, 例如上面的数据只有三层深度, 如果扩展为 10 层的话函数仍然可以适用. 

这个题目的其实就是一个树的遍历, 然后返回这个遍历路径. 但是想了半天没想到如何写

[zakarycode]

递归考虑下

[Chrisssss]

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

[geehero]

To iterate is human, to recurse divine.

[lyshine]

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

[voidbit]

用栈吖，回溯法

[asukanoir]

@lyshine 虽然好多年不写代码了。。。给个愚见：利用栈的思路，执行递归，先深度再广度，然后返回的时候上层调用函数自然会保留父节点路径，按说没有你说的这种问题吧。

[wly19960911]

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], '');

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

[noviceiOS]

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"));

[lyshine]

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

[noviceiOS]

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"));

[lyshine]

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

[shyling]

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

[Laumm]

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

[Laumm]

query(data[0],"name")

[Aliennnnnn]

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, '');

[geelaw]

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

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

[Sapp]

```
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"]

```

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

[jjwjiang]

这不就是最纯粹的递归吗？怎么看楼上一堆还传 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");

[zqx]

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

[panshao]

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', ''));