第 92 题：已知数据格式，实现一个函数 fn 找出链条中所有的父级 id
const value = '112'
const fn = (value) => {}
fn(value) // 输出 [1， 11， 112]
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
const value = '112'
const fn = (value) => {}
fn(value) // 输出 [1， 11， 112]
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（58）
const data = [{ id: '1', name: 'test1', children: [ { id: '11', name: 'test11', children: [ { id: '111', name: 'test111' }, { id: '112', name: 'test112' } ] }, { id: '12', name: 'test12', children: [ { id: '121', name: 'test121' }, { id: '122', name: 'test122' } ] } ] }]; let res = []; const findId = (list, value) => { let len = list.length; for (let i in list) { const item = list[i]; if (item.id == value) { return res.push(item.id), [item.id]; } if (item.children) { if (findId(item.children, value).length) { res.unshift(item.id); return res; } } if (i == len - 1) { return res; } } }; // res = [] findId(data, '123'); // res = [ '1' ] findId(data, '1'); // res = [ '1', '12' ] findId(data, '12'); // res = [ '1', '12', '122' ] findId(data, '122');评论好多直接复制黏贴都是错的，发之前先测试一下啊，另外如果按照示例中省市区id的规则，可以找到目标 id 然后直接推倒出所有父 id 的吧....
let res = [] let value = '112' for(let i = 0;i<value.length;i++){ res.push(value.slice(0,i+1)) } console.log(res)const value = '112'
const fn = (value) => {
let vals = value.split('');
//1 11 112
for (let i = 0; i < vals.length; i++) {
let v = vals.slice(0,i+1).join('')
console.log(v)
}
}
fn(value)
const bfs = data => { const queue = [...data] let res = [] while(queue.length) { let node = queue.shift() if (node.children) { for (let child of node.children) { queue.push(child) } res.push(node.id) } } return res }仔细看了下题目意图应该是通过这个id值 解析出所有父级链路，但是根据数据截图，这样推演下去34个省 可能会出现 3411 34512 这就没法玩了 省应该至少占两位 01 - 34 ； 为了出题而出的题 ，没有实用价值
const tree = { id: '1', name: 'test1', children: [ { id: '11', name: 'test11', children: [ { id: '111', name: 'test111' }, { id: '112', name: 'test112' } ] }, { id: '12', name: 'test12', children: [ { id: '121', name: 'test121' }, { id: '122', name: 'test122' } ] } ] }; interface Area { id: string, name: string, children?: Array<Area> }; function findAllParentId(tree: Area, id: string) { const stack = [tree]; while(stack.length > 0) { const top = stack.slice().pop(); if (top.id === id) break; if (top.children && top.children.length>0) { const cTop = top.children.pop(); stack.push(cTop); } else { stack.pop(); } } return stack.map(n => n.id); } const deepCopy = obj => JSON.parse(JSON.stringify(obj)); const idList = findAllParentId(deepCopy(tree), '122'); console.log(`${idList}`);经典数据结构的深度遍历结构
为什么运行结果不对
@wangyuanyuan0521
@ZodiacSyndicate
function fn(data, value) { let res = [] const dfs = (arr, temp = []) => { for (const node of arr) { if (node.id === value) { res = temp return } else { node.children && dfs(node.children, temp.concat(node.id)) } } } dfs(data) return res }const cityData = [{ id: '1', name: '广东省', children: [ { id: '11', name: '深圳市', children: [ { id: '111', name: '南山区' }, { id: '112', name: '福田区', children: [{ id: '1121', name: 'A街道' }] } ] }, { id: '12', name: '东莞市', children: [ { id: '121', name: 'A区' }, { id: '122', name: 'B区', } ] } ] }]; const tarId = '1121' const findId = (data, tarId, parentId = []) => data.reduce((acc, item) => acc.concat(item.id == tarId ? [...parentId, item.id] : item.children ? findId(item.children, tarId, [...parentId, item.id]) : []) , []) let res = findId(cityData, tarId) // 输出 [1, 11, 112, 1121] console.log(res)源码
const fn = (value, radix = 1) => Array.from(new Array(value.length / radix)).reduce( (al, _, idx) => [...al, value.slice(0, radix * (idx + 1))], [] );测试
fn('112') // ["1", "11", "112"] fn('123456789', 3) // ["123", "123456", "123456789"]解释
用途：用来把地址串转换为地址数组，常用于地址选择器，这里支持任何方式分割（常用于6 位地址每两位分割一次）
原理很简单，字符串是有规律的（每个更详细串包含父级串），就是简单的字符串分割（循环每次取前radix*(idx+1)范围的子串）
其实我也想问这个问题：
const arr = [ { id: 1, name: '广东', children: [ { id: 11, name: '深圳', children: [ { id: 111, name: '南山区' }, { id: 112, name: '福田区' } ] } ] } ] const id = 112 const fn = (treeData, idsList = [], ids = []) => { treeData.forEach(item => { const { id, children } = item const tempIds = [].concat(ids) tempIds.push(id) idsList.push(tempIds); if (children && !!children.length) { fn(children, idsList, tempIds); } }); return idsList; }; const list = fn(arr) const result = list.filter(item => { const lastValue = item[item.length - 1] return Number(lastValue) === Number(id) })思路：
1、将数组转换为多个一维数组，结果如下所示：
2、循环第一步所得的结果，判断最后一位是不是和要查询的id相同，如果是那么就返回结果
为了可读性，牺牲了部分复杂度。
代码：
function fn(id, list) { const match = list.find(item => item.id === id); if (match) return [id]; const sub = list.find(item => id.startsWith(item.id)); return [sub.id].concat(fn(id, sub.children)); }刚好有类似需求，试完答案竟然基本都是错的，自己试试。
不知道这样可以不
思路是每次遍历之前都利用结构记录一下层级，如果知道对应的id，直接返回即可
`const list = [{
id: '1',
name: '广东省',
children: [{
id: '11',
name: '深圳市',
children: [{
id: '111',
name: '南山区'
},
{
id: '112',
name: '福田区'
}
]
}]
}]
const value = '112'
const fn = (value, list) => {
let queue = [...list], res = [], level = 0
while(queue.length) {
debugger
let length = queue.length
for (let i = 0; i < length; i++) {
let node = queue.shift()
if (node.id === value) {
res.push(node.id)
} else {
if (value.slice(0, level + 1) === node.id) {
res.push(node.id)
}
node.children && queue.push(...node.children)
}
}
level++
}
}
console.log(fn(value, list))`
广度优先遍历
if (node.id === value) {
temp.push(node.id)
res = temp
return
}
var value = '112' let res = [] function fn(data, temp = []) { for(node of data) { if(node.id === value) { res = temp break } if(node.children) { fn(node.children, [...temp, ...[node.id]]) } } return [...res, ...[value]] }// 回溯 function fn(list, value) { let res = [] function helper(list, node) { if (node.id === value) { res = [...list] return } if (!node.children || !node.children.length) { return } for (let item of node.children) { list.push(item.id) helper(list, item) list.pop() } } helper([], {children:list}) return res }function findFather(list, targetId, path = []) { const len = list.length; for (let i = 0; i < len; i++) { console.log(list[i].id); if (list[i].id === targetId) { path.push(targetId); break; } else if (list[i].children) { path.push(list[i].id); findFather(list[i].children, targetId, path); } else if (list[i].id !== targetId && i === len-1) { path.pop(); } } return path; }const info = [{ id: '1', name: '广东省', children: [{ id: '11', name: '深圳市', children: [{ id: '111', name: '南山区', }, { id: '112', name: '福田区' }] }] }]; const fn = (value) => { let res = null; const dfs = (data, path) => { data.forEach((item) => { if (item.id === value) { path.push(item.id); res = path; return; }; if (item.children) { path.push(item.id); dfs(item.children, path); } }); }; dfs(info, []); return res; };`var list = [{
id: '1',
children: [{
id: '11',
children: [{
id: '111'
}, {
id: '112'
}]
}, {
id: '12',
children: [{
id: '121'
}, {
id: '122'
}]
}]
}]
let result = [];
function findParentId(list2, val) {
for (let key of list2) {
console.log(key)
if (key.id === val) {
result.push(key.id);
return result;
}
if (key.children) {
result.push(key.id);
let re = findParentId(key.children, val);
if (re && re.length) {
return re;
} else {
result.pop();
}`
function fnBFS(list, target) {
let resMap = {}
console.log(resMap)
let res = ''
while(resMap[target]) {
res +=
${target} ->target = resMap[target]
if(!resMap[target]) {
res += target
}
}
console.log(res)
}
前缀树 Trie，复杂度仅为需要查找value的长度：
const data = [ { id: "1", name: "test1", children: [ { id: "11", name: "test11", children: [ { id: "111", name: "test111" }, { id: "112", name: "test112" } ] }, { id: "12", name: "test12", children: [ { id: "121", name: "test121" }, { id: "122", name: "test122" } ] } ] } ] function find(arr, value) { let map = new Map() recursion(arr, [], map) console.log(map) return map.get(value); } function recursion(arr, parentArr, map) { arr.forEach(item => { let _parentArr = parentArr.slice() _parentArr.push(item.id) map.set(item.id, _parentArr); if (item.children && item.children.length > 0) { recursion(item.children, _parentArr, map) } }) } console.log(find(data, '122'))let list = [{
id: '1',
value: '四川省',
children: [{
id: '11',
value: '成都市',
children: [{
id: '111',
value: '高新区'
}, {
id: '112',
value: '天府新区'
}]
}]
}, {
id: '2',
value: '四川省',
children: [{
id: '21',
value: '成都市',
children: [{
id: '211',
value: '高新区'
}, {
id: '212',
value: '天府新区'
}]
}]
}];
function fn(list, id) {
let res = []
function search(list, res) {
let searched = false;
for (let node of list) {
if (node.id === id) {
res.push(node.id)
return true
} else {
if (node.children) {
res.push(node.id)
searched = search(node.children, res);
if (searched) {
return true
}
}
}
}
if (!searched) {
res.pop()
return false
}
}
search(list, res);
return res
}
console.log(fn(list, '212'))
const find04 = (arr, val) => {
let carr = {}
let func = (list, label) => {
list.forEach((item, index) => {
if (carr[label]) {
carr[item.id] = carr[label] + ',' + item.id
} else {
carr[item.id] = item.id
}
if (item.children && item.children.length > 0) {
}
这好像没提前返回吧？找到了不需要继续递归了
// 跟之前总结的树路径查找一个道理
const treePath = (tree, fn) => { const path = [], result = []; (function forNode(list = [...tree]){ list.forEach(node => { path.push(node.id) if (fn(node)) result.push(...path) node.children && forNode(node.children) path.pop() }) })() return result } console.log(treePath(tree, node => node.id === '212'))dfs + 回溯
const value = '1221' const data = [ { id: '1', name: '广东省', children: [ { id: '11', name: '深圳市', children: [ { id: '111', name: '南山区', }, { id: '112', name: '福田区', children: [ { id: '1121', name: 'test', }, ], }, ], }, { id: '12', name: '广州市', children: [ { id: '121', name: '天河区', }, { id: '122', name: '番禺区', children: [ { id: '1221', name: 'test', }, ], }, ], }, ], }, ] function fn(value) { function dfs(cur, value, res) { if (!cur) { return null } res.push(cur.id) if (cur.id === value) { return res } if (cur.children && cur.children.length) { for (let node of cur.children) { var result = dfs(node, value, res) if (result) return result } } res.pop() } for (let item of data) { var result = dfs(item, value, []) if (result) { return result } } return [] } console.log(fn(value)) // 输出 [ '1', '12', '122', '1221' ]const data = [{ id: '1', children: [{ id: '11', children: [{ id: '111', }, { id: '112', } ] }, { id: '12', children: [{ id: '121', }, { id: '122', } ] } ] }, { id: '2', children: [{ id: '21', children: [{ id: '211', }, { id: '212', } ] }, { id: '22', children: [{ id: '221', }, { id: '222', } ] } ] }]; function traverse(id, data, arr = []) { if (data.id === id) { arr.push(data) arr.done = true return arr } if (data.children) { for (const item of data.children) { const result = find(id, item, [...arr, data]) if (result && result.done) { return result } } } } function traverseAll(id, data) { for (const item of data) { const result = traverse(id, item) if (result) { return result.reduce((res, cur) => [...res, cur.id], []) } } } const result = traverseAll("221", data) console.log(result);const solution = (data = [], id) => { const stack = []; for (let i = 0; i < data.length; i += 1) { stack.push(data[i]); while (stack.length) { const curr = stack.pop(); if (curr.id === id) return curr.path; if (curr.children?.length) { const path = curr.path || [curr.id]; stack.push( ...curr.children.map((c) => ({ ...c, path: path.concat(c.id) })) ); } } } return []; }; const data = [ { id: "1", name: "test1", children: [ { id: "11", name: "test11", children: [ { id: "111", name: "test111" }, { id: "112", name: "test112" } ] }, { id: "12", name: "test12", children: [ { id: "121", name: "test121" }, { id: "122", name: "test122" } ] } ] }, { id: "2", name: "test1", children: [ { id: "21", name: "test11", children: [ { id: "211", name: "test111" }, { id: "212", name: "test112" } ] }, { id: "22", name: "test22", children: [ { id: "221", name: "test221" }, { id: "222", name: "test222" } ] } ] } ]; console.log(solution(data, "122")); console.log(solution(data, "222"));dfs
export default class FindChildParentIds { static data:Array<DataI> = [{ id: '1', name: 'test1', children: [ { id: '11', name: 'test11', children: [ { id: '111', name: 'test111' }, { id: '112', name: 'test112' } ] }, { id: '12', name: 'test12', children: [ { id: '121', name: 'test121' }, { id: '122', name: 'test122' } ] }, { id: '13', name: 'test13', children: [ { id: '131', name: 'test121' }, { id: '132', name: 'test122' } ] } ] }]; test() { console.log('find child parent Ids') const parents = FindChildParentIds.dFCPIds('131') console.log(parents); } static dFCPIds(id: string):string{ // 1 查找父节点 const p = this.findChildRPid(id,this.data,'') // 3 返回结果 return p } // 递归算法 static findChildRPid(id:string,ch: Array<DataI>,pL: string): any { let str = '' for (const node of ch){ if(node.id === id){ return pL +' '+ id; } else if (node.children) { str = pL + ' ' + node.id str = this.findChildRPid( id, node.children, str) } } return str } }---> 1 13 131
回朔法
const data = [{ id: 1, name: '广东', children: [{ id: 11, name: '深圳市', children: [{ id: 111, name: '南山区' }, { id: 112, name: '福田区' }] }] }, { id: 2, name: '湖南', children: [{ id: 22, name: '郴州市', children: [{ id: 222, name: '桂阳' }, { id: 223, name: '燕塘' }] }] }] const getParents = (val, arr = []) => { for (let i in arr) { // 找到当前目标节点 if (arr[i].id === val) { return [false] } if (arr[i].children) { const parentIdArr = getParents(val, arr[i].children) // parentIdArr 不为空，说明找到了目标节点，当前节点为目标节点的子节点 if (parentIdArr.length) { return parentIdArr[0] ? [arr[i].id, ...parentIdArr ] : [arr[i].id] } } } return [] } console.log(getParents(112, data))深度优先
/** * dfs * @author waldon * @date 2022-04-08 * @param {*} value - param * @param {*} arr - param */ function getArr(value, arr) { function getChildren(_arr, path = []) { for (const item of _arr) { if (item.id === value) { path.push(item.id) return path } else if (item.children) { path.push(item.id) return getChildren(item.children, [...path]) } } } return getChildren(arr) } const data = [ { id: '1', name: 'test1', children: [ { id: '11', name: 'test11', children: [ { id: '111', name: 'test111', }, { id: '112', name: 'test112', }, ], }, { id: '12', name: 'test12', children: [ { id: '121', name: 'test121', }, { id: '122', name: 'test122', }, ], }, ], }, ] console.log(getArr('112', data))简单的回溯，找到之后停止继续查找
function findParents(id, data) { let res; const path = []; backTrack(data); return res; function backTrack(arr) { if (res) return; for (let i = 0; i < arr.length; i++) { if (arr[i].id === id) { path.push(id); res = [...path]; return; } if (arr[i].children) { path.push(arr[i].id); backTrack(arr[i].children); path.pop(); } } } } const data = [{ id: '1', name: 'test1', children: [ { id: '11', name: 'test11', children: [ { id: '111', name: 'test111' }, { id: '112', name: 'test112' } ] }, { id: '12', name: 'test12', children: [ { id: '121', name: 'test121' }, { id: '122', name: 'test122' } ] } ] }]; console.log(findParents('112', data));写法是深度优先， 增加了数据结构的深度与广度，能可以正确输出
const fn = (value) => { let graph = [] const mapData = new Map(); function ParentMap(data, parentId) { parentId = parentId || 0; data.forEach(item => { mapData[item.id] = { ...item, parentId } if (item.children) { ParentMap(item.children, item.id); } }) } ParentMap(data) function getId(data, value) { graph.unshift(data[value].id) if (data[value].parentId !== 0) { getId(data, data[value].parentId) } } getId(mapData, value) return graph; }刚刚好，中间仅仅差了一个数组方法：
function bfs(target, id) { const quene = [...target] do { const current = quene.shift() if (current.children) { quene.push(...current.children.map(x => ({ ...x, path: (current.path || current.id) + '-' + x.id }))) } if (current.id === id) { return current } } while(quene.length) return undefined } function dfs(target, id) { const stask = [...target] do { const current = stask.pop() if (current.children) { stask.push(...current.children.map(x => ({ ...x, path: (current.path || current.id) + '-' + x.id }))) } if (current.id === id) { return current } } while(stask.length) return undefined } // 公共的搜索方法，默认bfs function commonSearch(target, id, mode) { const staskOrQuene = [...target] do { const current = staskOrQuene[mode === 'dfs' ? 'pop' : 'shift']() if (current.children) { staskOrQuene.push(...current.children.map(x => ({ ...x, path: (current.path || current.id) + '-' + x.id }))) } if (current.id === id) { return current } } while(staskOrQuene.length) return undefined }@ZodiacSyndicate
这个写法想查112的时候不就查不出来了..
嗯我再研究一下~
var list = [{ id: '1', children: [{ id: '11', children: [{ id: '111' }, { id: '112' }] }, { id: '12', children: [{ id: '121' }, { id: '122' }] }] }] const value = '122';这个情景不太对吧
let list = [{ id: '1', children: [{ id: '11', children: [{ id: '111' }, { id: '112' }] }] }]; function fn(value) { // 回溯的标记 let _p = Symbol('parent'); // 找到子节点 let result; function _fn(arr, p) { for (let i = 0; i < arr.length; i++) { arr[i][_p] = p; if (arr[i].id === value) { result = arr[i]; return; } !result && arr[i].children && _fn(arr[i].children, arr[i]) } if (result) return; } _fn(list, null); let tmp = []; if (!result) return null; while (result) { tmp.unshift(result.id); result = result[_p]; } return tmp; }思路是找到子节点，再回溯找父节点
复杂度是O(n)，循环n次子节点，但是需要额外空间记录父节点引用
dfs
const fn = (data, value) => { let res = [] const dfs = (arr, temp = []) => { for (const node of arr) { if (node.children) { dfs(node.children, temp.concat(node.id)) } else { if (node.id === value) { res = temp } return } } } dfs(data) return res }const data = [{ id: '1', name: 'test1', children: [ { id: '11', name: 'test11', children: [ { id: '111', name: 'test111' }, { id: '112', name: 'test112' } ] }, { id: '12', name: 'test12', children: [ { id: '121', name: 'test121' }, { id: '122', name: 'test122' } ] } ] }]; const find = (value) => { let result = []; let findArr = data; let skey = ''; for (let i = 0, l = value.length; i < l; i++) { skey += value[i] let item = findArr.find((item) => { return item.id == skey }); if (!item) { return []; } result.push(item.id); if (item.children) { findArr = item.children; } else { if (i < l - 1) return [] return result; } } } //调用看结果 function testFun() { console.log('1,11,111:', find('111')) console.log('1,11,112:', find('112')) console.log('1,12,121:', find('121')) console.log('1,12,122:', find('122')) console.log('[]:', find('113')) console.log('[]:', find('1114')) }