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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2043 天前的主题，其中的信息可能已经有所发展或是发生改变。

题目是:

给一个数据结构如下
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 层的话函数仍然可以适用. 

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

30 条回复 • 2023-05-18 10:59:39 +08:00

zakarycode

2019-05-21 09:47:54 +08:00

递归考虑下

Chrisssss

2019-05-21 09:50:13 +08:00

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

geehero

2019-05-21 09:50:33 +08:00 via iPhone

To iterate is human, to recurse divine.

lyshine

2019-05-21 10:05:06 +08:00

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

voidbit

2019-05-21 10:09:36 +08:00 via iPhone

用栈吖，回溯法

asukanoir

2019-05-21 10:11:34 +08:00

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

wly19960911

2019-05-21 10:35:55 +08:00

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

2019-05-21 10:49:13 +08:00

lyshine

2019-05-21 10:53:25 +08:00

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

noviceiOS

2019-05-21 10:59:52 +08:00

lyshine

2019-05-21 11:01:29 +08:00

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

shyling

2019-05-21 11:16:29 +08:00

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

Laumm

2019-05-21 11:39:38 +08:00

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

2019-05-21 11:43:58 +08:00

query(data[0],"name")

Aliennnnnn

2019-05-21 11:50:57 +08:00

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

2019-05-21 12:19:48 +08:00 via iPhone

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

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

Sapp

2019-05-21 12:21:31 +08:00

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

2019-05-21 13:41:30 +08:00

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

2019-05-21 13:47:38 +08:00 via Android

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

panshao

2019-05-21 14:41:55 +08:00

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

poisedflw

2019-05-21 15:26:07 +08:00

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

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

nikandaoleshenme

2019-05-21 16:38:33 +08:00

@lyshine 竟然从这跑去 sf 了

redbuck

2019-05-21 17:09:35 +08:00

递归就完了
```
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

2019-05-21 17:22:11 +08:00

@redbuck

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

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

lyshine

2019-05-21 18:01:58 +08:00

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

lyshine

2019-05-21 19:26:54 +08:00

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

lyshine

2019-05-21 19:35:47 +08:00

@zqx 错了 , 是 8 楼的实现

aihimmel

2019-05-21 23:55:55 +08:00

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']

brucewuio

2019-05-24 15:06:34 +08:00

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']
}
}
}
}

takemyhate

2023-05-18 10:59:39 +08:00

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 变量中。最终返回得到的路径。这个可以适用于多层的数据结构，因为它通过递归方式遍历树的每个节点，不论树的深度有多大，都能正确地找到路径。