问个 js 算法题

V2EX = way to explore

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

现在注册

已注册用户请登录

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

const treeData = [
  {
    id: 1,
    children: {
      id: 2,
      children: {
        id: 3
      }
    }
  },
  {
    id: 4,
    children: {
      id: 5,
      children: {
        id: 6
      }
    }
  }
]

// 2 1-2-3 1 1-2-3 3 1-2-3 结构给个 ID 输出上下级

9 条回复

hello2090

2022-02-21 11:55:14 +08:00

虽然我 leetcode 刷了 500 多题，但我真看不太懂这题的意思。。

murmur

2022-02-21 11:56:56 +08:00

你的 children 不能带一个指针指向 parent 么

wenzichel

2022-02-21 12:00:07 +08:00

只能遍历了吧

cxe2v

2022-02-21 12:05:22 +08:00

有点像链表

Kasumi20

2022-02-21 12:18:08 +08:00

function findIndex(id) {
try {
treeData.forEach((item, index) => {
var child = item;
while (true) {
if (child.id === id) {
throw index;
}
if (typeof child.children !== 'object') {
break;
}
child = child.children;
}
});
} catch (index) {
return index;
}
return -1;
}

function getStruct(index) {
var child = treeData[index];
var ids = [];
while (true) {
if (typeof child.id === 'number') {
ids.push(child.id);
}
if (typeof child.children !== 'object') {
break;
}
child = child.children;
}
return ids;
}

function test(id) {
var index = findIndex(id);
var ids = getStruct(index);
console.log(id + ' ' + ids.join('-'));
}

test(1);
test(2);
test(6);

/*
1 1-2-3
2 1-2-3
6 4-5-6
*/

chairuosen

2022-02-21 12:21:46 +08:00

这结构不是 tree 这是两根电线杆啊

aikilan

2022-02-21 13:35:54 +08:00

遍历递归，谈不上算法，简单暴力，毫无意义

nowgoo

2022-02-21 14:49:12 +08:00

投机一下

const output = function(treeData, n){
let flat = e => e.children ? e.id + "-" + flat(e.children) : e.id,
flatted = treeData.map(flat).map(e => "-"+ e +"-").join(',');
return flatted.match(new RegExp('[^,]*-'+ n +'-[^,]*'))[0]
.replace(/^-+/, '')
.replace(/-+$/, '');
}

jguo

2022-02-21 15:19:50 +08:00

你这算哪门子 children