# JS算法题目3

Lambo
• 284
``````let tree = [
{
name: 'A',
childs:[
{
name:'1001',
childs:[
{
name:'1002',
childs:[
{
name:'1003',
childs:[]
}
]
}
]
}
]
},
{
name: 'B',
childs:[
{
name:'1004',
childs:[
{
name:'1005',
childs:[]
}
]
}
]
}
]``````

//要求：给定一个树形数据结构，输入任何一个 子元素，返回他的根级元素
/**

...
*/

##### 3个回答
✓ 已被采纳
``````function findRoot(list, cb) {
for(var item of list) {
if(cb(item) || (item.childs && findRoot(item.childs, cb))) return item;
}
return null;
}

findRoot(tree,item => item.name == 'A')
findRoot(tree,item => item.name == '1001')``````
``````const createTreeNodeFinder = (treeData) => {
const memorizedNodes = new Map();

const collect = (treeData, name) => {
const path = [];
const dummyRoot = {
name: "",
childs: treeData
};

const helper = (root, path) => {
if (!root) return false;

if (root.name && !memorizedNodes.has(root.name)) {
memorizedNodes.set(root.name, root);
}

path.push(root);

if (root.name === name) {
return true;
}

for (let i = 0; i < root.childs.length; ++i) {
root.childs[i]._parent = root;
if (helper(root.childs[i], path)) return true;
}

path.pop();
};

helper(dummyRoot, path);
path.shift();

return path;
};

const collectNodeToRoot = (node) => {
const res = [];

let parent = node._parent;
while (parent) {
res.push(parent);
parent = parent._parent;
}

//去掉dummyRoot
res.pop();
res.reverse();

return res;
};

return (name) => {
const node = memorizedNodes.get(name);

if (!node) {
console.log("slow path");
return collect(treeData, name)?.[0].name ?? "";
} else {
console.log("fast path");
return collectNodeToRoot(node)?.[0]?.name ?? "";
}
};
};

const finder = createTreeNodeFinder(tree);

console.log(finder("A"));
console.log(finder("1001"));
console.log(finder("1002"));
console.log(finder("1003"));
console.log(finder("B"));
console.log(finder("1004"));
console.log(finder("1005"));
``````
``````function solution(list, target, level = 0, result) {
for(item of list) {
if (item.name === target) return level === 0 ? target : result

if (Array.isArray(item.childs)) {
result = level === 0 && !result ? item.name : result
solution(item.childs, target, level + 1, result)
}
}

return result
}

console.log('solution: ', solution(tree, 'A'));
console.log('solution: ', solution(tree, '1003'));``````
##### 撰写回答
###### 你尚未登录，登录后可以
• 和开发者交流问题的细节
• 关注并接收问题和回答的更新提醒
• 参与内容的编辑和改进，让解决方法与时俱进