Daily-Interview-Question
Daily-Interview-Question copied to clipboard
Published
20 hours ago •
Advanced-Frontend
Advanced-Frontend
第 92 题：已知数据格式，实现一个函数 fn 找出链条中所有的父级 id
const value = '112'
const fn = (value) => {
...
}
fn(value) // 输出 [1， 11， 112]
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'))
}
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
}
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次子节点，但是需要额外空间记录父节点引用
const findItem = (value, list, graph) => { return list.some(item => { if (item.id === value) { graph.push(item.id) return true } if (item.children) { graph.push(item.id) return findItem(value, item.children, graph) } }) } const fn = value => { let graph = [] list.some(item => { graph.push(item.id) if (item.id === value) return true if (item.children) { let res = findItem(value, item.children, graph) if (!res) graph = [] return res } }) return graph }实现的思路是记录每次 dfs 遍历的路径，当找到元素时，返回记录的所有路径，找不到时清空路径遍历下个元素
希望有更好的解法
var list = [{
id: '1',
children: [{
id: '11',
children: [{
id: '111'
}, {
id: '112'
}]
}, {
id: '12',
children: [{
id: '121'
}, {
id: '122'
}]
}]
}]
const value = '122';
这个情景不太对吧
const findItem = (value, list, graph) => { return list.some(item => { if (item.id === value) { graph.push(item.id) return true } if (item.children) { graph.push(item.id) return findItem(value, item.children, graph) } }) } const fn = value => { let graph = [] list.some(item => { graph.push(item.id) if (item.id === value) return true if (item.children) { let res = findItem(value, item.children, graph) if (!res) graph = [] return res } }) return graph }实现的思路是记录每次 dfs 遍历的路径，当找到元素时，返回记录的所有路径，找不到时清空路径遍历下个元素 希望有更好的解法
var list = [{ id: '1', children: [{ id: '11', children: [{ id: '111' }, { id: '112' }] }, { id: '12', children: [{ id: '121' }, { id: '122' }] }] }] const value = '122';这个情景不太对吧
嗯我再研究一下~
- bfs利用队列实现，循环中做的是push => shift => push => shift
- dfs利用栈实现，循环中做的是push => pop => push => pop
刚刚好，中间仅仅差了一个数组方法：
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
}
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;
}
/*
* 已知数据格式，实现一个函数 fn 找出链条中所有的父级 id
* 实现： 通过es6的class实现，思路：递归调用，下传当前的父辈的id
*/
class FindFather{
constructor() {
this.data = this.init(),
this.target = null;
}
dfs(value,data,idArr) {
var that = this;
data.forEach((item, index) => {
item.idArr = idArr.concat(item.id)
if(item.id === value) {
this.target = item.idArr;
}
if(item.children){
return this.dfs(value, item.children, item.idArr)
}
})
}
result() {
return this.target;
}
init() {
return [{
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'
}
]
}
]
}];
}
}
var find = new FindFather();
find.dfs('112',find.data, [])
console.log(find.result()) //["1","12","121"]
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',
children: [
{
id: '1221',
name: 'test121',
children:[
{
id:'12345'
}
]
}
]
}
]
}
]
},
{
id:'1234',
children:[
{
id:'567'
}
]
}
]
const value = '112'
const fn = (value) => {
let err = 'return start'
let interim = JSON.parse(JSON.stringify(data))
let result = []
try {
while (interim.length > 0) {
let point = interim.pop()
let child = point.children
let queue = child
let cresult = []
result.push(point.id)
while (queue && queue.length > 0) {
let cpoint = queue.pop()
cresult.push(cpoint.id)
if (!cpoint.children || cpoint.id == value) {
if (cresult.indexOf(value) > -1) {
queue.length = 0
} else {
cresult = []
}
continue
}
queue.push(...cpoint.children)
}
if (result.concat(cresult).indexOf(value) > -1) {
result = result.concat(cresult)
throw new Error(err)
} else {
result = []
}
}
} catch (e) {
if (e.message === err) {
console.log(result.map(v => parseInt(v)))
return result.map(v => parseInt(v))
} else {
throw e
}
}
}
fn(value) // 输出 [1， 11， 112]
fn('1234') // 输出 [1234]
fn('12345') // 输出 [1, 12, 121, 1221, 12345]
写法是深度优先， 增加了数据结构的深度与广度，能可以正确输出
function dfsFn(list, value) {
let res = []
function dfs(arr, ids=[]) {
for (const item of arr) {
if (item.id === value) {
res = [...ids, ...[item.id]]
return
} else {
if (item.children) {
dfs(item.children, ids.concat([item.id]))
}
}
}
}
dfs(list)
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'
}
]
}
]
}];
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');
function getIdChain(data, id, idkey = "id", childrenKey = "children") {
if (check(data, id)) {
return [];
}
loop.chain = [];
loop(data, id);
return loop.chain;
function check(data, id) {
return !Array.isArray(data) || !data.length || (!id && id !== 0);
}
function loop(arr, v) {
if (check(arr, v)) {
return false;
}
return arr.some(i => {
return i[idkey] === v || (i[childrenKey] && loop(i[childrenKey], v))
? (loop.chain.unshift(i[idkey]), true)
: false;
});
}
}
评论好多直接复制黏贴都是错的，发之前先测试一下啊，另外如果按照示例中省市区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 fn = (str) => [...str].reduce((prev, next) => [...prev, prev.slice(-1) + next], [])
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的规则，可以找到目标 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)
仔细看了下题目意图应该是通过这个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}`);
经典数据结构的深度遍历结构
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 }
为什么运行结果不对
@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)范围的子串）
评论好多直接复制黏贴都是错的，发之前先测试一下啊，另外如果按照示例中省市区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)
其实我也想问这个问题：
- 如果id是有规律的，最容易处理，通过id解析出结果， 其他情况的重点是优先找到目标节点
- 如果id的位数和层级有关系， 处理方法就要根据id，判断不同的层级， 做不同的处理（少很多递归）
- 如果id和层级没有关系，就需要权衡是深度优先还是广度优先做处理
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));
}
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',
children:[
{
id: '1221',
name: 'test121'
},
]
}
]
}
]
}];
function findValue(data,valie){
var key = [];
function find (data,value){
for(let i=0; i<data.length;i++){
if(data[i].id === value){
key.push(data[i].id)
break
}
if(data[i].children && data[i].children.length > 0){
if(find(data[i].children,value).length > 0){
key.push(data[i].id)
break;
}
}
}
return key
}
find(data,valie)
return key
}
console.log(findValue(data,'1221'))
刚好有类似需求，试完答案竟然基本都是错的，自己试试。
const data = [{
id: 1,
children: [{
id: 2,
children: [{
id: 3
}, {
id: 4
}]
}]
}];
let find = (function () {
let map = null;
let findMap = (data, ids, map = {}) => {
data.forEach(item => {
map[item.id] = map[item.id] || [];
if (ids) {
map[item.id] = ids.concat(item.id);
} else {
map[item.id].push(item.id);
}
if (item.children) {
return findMap(item.children, map[item.id], map);
}
});
return map;
}
return function (value) {
if (!map) {
map = findMap(data);
}
return map[value];
}
})();
console.log(find(1)) // [1]
console.log(find(2)) // [1, 2]
console.log(find(3)) // [1, 2, 3]
console.log(find(4)) // [1, 2, 4]
'use strict';
/**
* @description: 典型的树状结构遍历算法，从某顶点到某顶点的深度优先算法。
* 遍历顶点V的相邻节点，如果子节点有孙节点则递归遍历孙节点
* 用一个栈来存储路径。
* @author: zpp
* @date: 2019-07-16
*/
const province = [
{
id: "1",
name: "广东省",
children: [
{
id: "11",
name: "深圳市",
children: [
{id: "111", name: "罗湖区"},
{id: "112", name: "南山区"},
{id: "113", name: "福田区", children: [{id:'1131',name:'下沙'}]}
]
}, {
id: "12",
name: "惠州"
},
{
id: "13",
name: "广州",
children: [{id:'131',name:'花都'}]
}
]
}
]
let fnc = (value) => {
let res = [] // 用来存放最终路径
let dfs = function(arr, path=[]){
for(let item of arr ){ // 遍历顶点的所有邻居节点
if(item.id === value){
path.push(item.id) // 将最后一个路径存进去，返回找到的路径，并退出循环
res = path
return
}else{
console.log('push_stack_id:', item.id)
path.push(item.id)
if(item.children){
dfs(item.children, path)
}else{
let _popNoChild = path.pop()
console.log('pop_no_child: ',_popNoChild)
}
}
}
if(!res.length){
let _popCurrentNode = path.pop()
console.log('pop_current_node:', _popCurrentNode)
}
}
dfs(province)
console.log('res',res)
return res
}
fnc('131')
深度优先遍历（DFS）
var resABC = [
{
"id": 1,
"name": "部门A",
"parentId": 0,
"children": [
{
"id": 3,
"name": "部门C",
"parentId": 1,
"children": [
{
"id": 6,
"name": "部门F",
"parentId": 3
}
]
},
{
"id": 4,
"name": "部门D",
"parentId": 1,
"children": [
{
"id": 9,
"name": "部门H",
"parentId": 4
},
{
"id": 8,
"name": "部门HH",
"parentId": 4
}
]
}
]
},
{
"id": 2,
"name": "部门B",
"parentId": 0,
"children": [
{
"id": 5,
"name": "部门E",
"parentId": 2
},
{
"id": 7,
"name": "部门G",
"parentId": 2
}
]
}
];
const fn = function (array, value) {
var flag = 0;
var result = [];
const findId = function (array, [...resParentIds]) {
for (let index = 0; index < array.length; index++) {
if (flag === 1) break;
const element = array[index];
if (index > 0) {
resParentIds.pop();
}
resParentIds.push(element.id);
if (element.id === value) {
flag = 1;
result = resParentIds;
break;
} else {
if (element.children) {
findId(element.children, resParentIds);
}
}
}
}
findId(array, []);
return result;
}
console.log(fn(resABC, 8)); // [1, 4, 8]
console.log(fn(resABC, 7)); // [2, 7]
console.log(fn(resABC, 5)); // [2, 5]
let list = [
{
id: '1',
name: '广东省',
children: [
{
id: '11',
name: '深圳市',
children: [
{
id:'111',
name: '南山区'
},
{
id:'112',
name: '福田区'
}
]
}
]
}
]
console.log(getp(list,'112'))
function getp(list,value) {
var arr = list.filter(() => true);
var _pid;
while (arr.length){
var val = arr.shift();
if(val.id === value){
_pid = null;
}else{
if(val.children){
for(let i = val.children.length-1;i>=0;i--){
if(val.pid){
val.children[i].pid = val.pid.concat([val.id])
}else{
val.children[i].pid = [val.id]
}
if(val.children[i].id === value){
_pid = val.children[i].pid;
_pid.push(value)
arr = [];
break;
}
arr.push(val.children[i])
}
}
}
}
if(!_pid){
console.log('没有父元素');
}
return _pid;
}
const list =[
{id:1,name:'部门A',parentId:0},
{id:2,name:'部门B',parentId:0},
{id:3,name:'部门C',parentId:1},
{id:4,name:'部门D',parentId:1},
{id:5,name:'部门E',parentId:2},
{id:6,name:'部门F',parentId:3},
{id:7,name:'部门G',parentId:2},
{id:8,name:'部门H',parentId:4}
];
const convert = (list, filters) => {
return list.map(item => {
let children = filters.filter(child => child.parentId === item.id)
if (children.length > 0) {
return {
...item,
children: convert(children, filters)
}
} else {
return item
}
})
}
let res = convert(list, list)
function findId(data,arr=[]) { for(let i=0;i<data.length;i++){ if(Object.keys(data[i]).includes('children')){ console.log(data[i]) arr.push(data[i].id) findId(data[i].children,arr) } } return 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',
children: [
{
id: '1211',
name: 'test1211',
}
]
},
{
id: '122',
name: 'test122'
}
]
}
]
}];
/**
*
* @param {*} data 输入数据
* @param {*} target 要找的id，默认它是全局唯一的
* @param {*} route 当前路径
* @param {*} depth 当前深度，route的长度要保持和它一样
* @return 如果找到就返回路径，否则没有返回值
*/
function dfs(data, target, route, depth){
for(let i=0; i<data.length; i++){
// 要保持路径长度和当前深度一致
if(route.length > depth) {
route = route.slice(0, depth);
}
route.push(data[i].id);
let new_depth = depth + 1; // 深度已经加一，这个深度用于下一个dfs调用
// console.log(new_depth, route); // 这个打印观察route的长度和new_depth的关系
if(data[i].id == target) return route; // 如果找到了目标，就直接返回route
if(data[i].children && data[i].children.length > 0){
let res = dfs(data[i].children, target, route, new_depth);
if(res) return res; // 如果递归的dfs找到了目标，返回递归dfs的返回值
}
}
}
/**
* 每次都复制route，就不用记录depth
* @param {*} data
* @param {*} target
* @param {*} route
*/
function dfs2(data, target, route){
for(let i=0; i<data.length; i++){
let new_route = route.slice(); // 每次都复制之前的route
new_route.push(data[i].id);
if(data[i].id == target) return new_route; // 如果找到了目标，就直接返回route
if(data[i].children && data[i].children.length > 0){
let res = dfs2(data[i].children, target, new_route);
if(res) return res; // 如果递归的dfs找到了目标，返回递归dfs的返回值
}
}
}
let t_list = ['1', '11', '12', '111', '112', '121', '122', '1211', '404'];
for(let i=0; i<t_list.length; i++){
console.log(t_list[i], dfs(data, t_list[i], [], 0));
console.log(t_list[i], dfs2(data, t_list[i], []));
}
const fn = (value, tree, newArr = []) => {
function fn1 (tree) {
if (value.startsWith(tree.id)) newArr.push(tree.id)
if (tree.id === value || !tree.children) return
for (const item of tree.children) {
fn(value, item, newArr)
}
}
if (tree instanceof Array) {
for (const item of tree) fn1(item)
} else {
fn1(tree)
}
return newArr
}
const tree = [{
id: '1',
name: '广东',
children: [{
id: '11',
name: '深圳',
children: [{
id: '111',
name: '南山区'
},
{
id: '112',
name: '福田区'
}
]
}]
}]
console.log(fn('112', tree))
function fn(data, id) {
const ref = []
const dfs = function(data, id) {
const quene = [...data]
while(quene.length > 0) {
const current = quene.shift()
if(current.id === id){
return ref.concat(current.id)
} else if(current.children) {
ref.push(current.id)
return dfs(current.children, id)
}
}
return undefined
}
return dfs(data, id)
}
let res = [];
let arr = [];
const findId = (data, id) => {
data.forEach((item, index) => {
if (item.children) {
if (item.id !== id) {
res.push(item.id);
findId(item.children, id);
}
}
arr.push(item.id);
})
arr.includes(id) === true ? res : res = [];
return res;
}
let func = function (value) { let newArr = []; let markAll = function (params, id) { params.forEach((i) => { if (i.children) { i.m_id = id markAll(i.children, i.id) } else { i.m_id = id } }) } markAll(data, undefined);//标记父级
let find = function (opt, upId) {
opt.forEach((i) => {
if (i.id === upId) {
newArr.unshift(i.id)
find(data, i.m_id)
} else {
if (i.children) {
find(i.children, upId)
}
}
})
}
find(data, value);// 调用查找父级
return newArr;
}
console.log( func(112));
class format {
constructor(data) {
this.res = [];
this.data = data;
this.start(data);
}
start(data) {
if(data instanceof Array) {
data.forEach(i => {this.start(i)})
}else if(data instanceof Object) {
if(data.id) {
this.res.push(data.id)
delete data.id
}
Object.values(data).forEach(i => {this.start(i)});
}else {
return this.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'
}
]
}
]
}];
console.log(new format(data).res)
// ["1", "11", "111", "112", "12", "121", "122"]
function Recursive_Path(data, value, path){ for( let i = 0; i< data.length; i++ ){ if(data[i].name === value){ return path.concat(data[i].id); }else{ if(data[i].children){ let child = data[i].children; let temp = path.concat(data[i].id); let result = Recursive_Path(child, value, temp); if(result) return result; else continue; }else{ continue; } } } }
let result = Recursive_Path(data, "test112", []);
function find(tree, value) {
var res;
if(findFathers(tree, value)){
return res;
}
else{
return undefined;
}
function findFathers(tree, value, stuck) {
stuck = stuck || [];
for (let child of tree) {
stuck.push(child.id);
if (child.id === value) {
//console.log(stuck);
res = stuck.slice();
return true;
}
if (child.children) {
if (findFathers(child.children, value, stuck)) {
return true;
}
}
stuck.pop();
}
return false;
}
}
- bfs利用队列实现，循环中做的是push => shift => push => shift
- dfs利用栈实现，循环中做的是push => pop => push => pop
刚刚好，中间仅仅差了一个数组方法：
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 }
为啥要返回undefined?
function getListLinksById(list, id) { const linkMap = {}; list = JSON.parse(JSON.stringify(list)); function _initLink(obj, parentIds) { obj.link = [...parentIds, obj.id]; linkMap[obj.id] = obj.link; if (Array.isArray(obj.children)) { obj.children.forEach(child => _initLink(child, obj.link)); } } list.forEach(item => _initLink(item, [])); return linkMap[id]; } console.log(getListLinksById(list, '111'));
const data = [{
id: '1',
name: '广东省',
children: [
{
id: '11',
name: '深圳市',
children: [
{
id: '111',
name: '南山区',
children: [
{
id: '115',
name: '未知'
}
]
},
{
id: '112',
name: '福田区'
}
]
},
{
id: '12',
name: '深圳市',
children: [
{
id: '113',
name: '南山区'
},
{
id: '114',
name: '福田区'
}
]
}
]
}];
/**
* 获取目标id的路径
* @param {string} target 查找目标id
* @param {array} arr 当前进行查找遍历的数据
* @param {array} path 当前路径
* @param {object} result
*/
const getPath = (target, arr, path, result) => {
for (let i = 0; i < arr.length; i++) {
const item = arr[i];
if (result.result) return
if (item.id === target) {
path.push(item.id)
result.result = path;
return
}
if (item.children && Array.isArray(item.children)) {
const curPath = [...path];
curPath.push(item.id);
getPath(target, item.children, curPath, result)
}
}
}
const fn = value => {
const result = {
result: null
};
getPath(value, data, [], result)
console.log(result.result)
}
fn('112') // => [ '1', '11', '112' ]
fn('115') // => [ '1', '11', '111', '115' ]
fn('114') // => [ '1', '12', '114' ]
再发一个吧，这才是递归的合理使用方案
const data = [{
id: '1',
name: '广东省',
children: [
{
id: '11',
name: '深圳市',
children: [
{
id: '111',
name: '南山区',
children: [
{
id: '115',
name: '未知'
}
]
},
{
id: '112',
name: '福田区'
}
]
},
{
id: '12',
name: '深圳市',
children: [
{
id: '113',
name: '南山区'
},
{
id: '114',
name: '福田区'
}
]
}
]
}];
/**
* 获取目标id的路径
* @param {string} target 查找目标id
* @param {array} arr 当前进行查找遍历的数据
*/
const getPath = (target, arr) => {
for (let i = 0; i < arr.length; i++) {
const item = arr[i];
if (item.id === target) {
return item.id
}
if (item.children && Array.isArray(item.children)) {
const nextId = getPath(target, item.children);
if (nextId) {
return item.id + '|' + nextId
}
}
}
}
const fn = value => {
const strResult = getPath(value, data);
const result = strResult.split('|');
console.log(result)
}
fn('112') // => [ '1', '11', '112' ]
fn('115') // => [ '1', '11', '111', '115' ]
fn('114') // => [ '1', '12', '114' ]
简单的回溯,用一个数组记录路径,在触达目标id时结束算法,此时算法走过的路径就是所有父级路径
//假设输入的id是正确的
function fn(id) {
let res, choices = arr, search_done = false;
bt([], choices);
function bt(trace, choices) {
if (search_done) return;//达到目的后应该终止回溯
if (trace[trace.length - 1] === id) { //终止条件:路径中最后一个id就是目标id
res = [...trace];//记得拷贝trace再赋值,因为路径可能还会被重写
search_done = true;//目的达成,标记一下,不再继续搜索
}
else {
for (let i in choices) {
trace.push(choices[i].id);//前进一步
bt(trace, choices[i].children)
trace.pop();//后退一步
}
}
}
return res;
}
//demo:
let arr = [
{
id: 1,
name: "广东",
children: [
{
id: 11,
name: "深圳市",
children: [
{
id: 111,
name: "南山区"
},
{
id: 112,
name: "福田区"
}
]
}, {
id: 12,
name: "广州市",
children: [
{
id: 121,
name: "xxx"
},
{
id: 122,
name: "aaa"
}
]
},
{
id: 13,
name: "广州市2",
children: [
{
id: 131,
name: "xxx2"
},
{
id: 132,
name: "aaa2"
}
]
}
]
}
];
console.log(fn(131))
function fn (list, id) {
function _fn (nodeList) {
for (let i = 0, len = nodeList.length; i < len; i++) {
const node = nodeList[i]
if (node.id == id) {
return [node.id]
}
if (node.children && node.children.length) {
const r = _fn(node.children)
if (r) {
return [node.id].concat(r)
}
}
}
}
return _fn(list)
}
基于递归的DFS，本身就是一种调用栈，在每个调用栈中，保存当前栈元素，再根据给定的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 fn (value) {
const result = [];
const dfs = (source) => {
for (let item of source) {
result.push(item);
if (item.id === value) {
return;
} else {
const res = dfs(item.children || []);
if (!res) return;
}
result.pop(item);
}
return true;
};
dfs(data);
return result.map(item => item.id);
}
fn("112") // ["1", "11", "112"]
let list = [{
id: 1,
name: "广东省",
children: [
{
id: 11,
name: "深圳市",
children: [
{
id: 111,
name: "南山区",
children: [
{
id: 110,
name: "沙河派出所",
children: [
{
id: 1101,
name: "世界之窗",
}
]
}
]
},
{
id: 112,
name: "福田区"
},
]
},
{
id: 22,
name: "广州市",
children: [
{
id: 114,
name: "越秀区"
}
]
}
]
},
{
id: 3,
name: "北京市",
children: [
{
id: 31,
name: "直辖区",
children: [
{
id: 311,
name: "东城区"
},
{
id: 312,
name: "西城区"
}
]
}
]
}];
const value = '112'
const fn = (value) => {
let arr = [[]];
let arrFloor = [];
let searchArr = [];
function parent(val) {
for (let i in val) {
if (!val[i].children) {
arrFloor.push([val[i].id]);
} else {
children(val[i], val[i].id).pop();
}
}
return arr.concat(arrFloor);
};
function children(val, id) {
for (let i in val.children) {
arr[arr.length - 1].push(val.id);
if (arr[arr.length - 1][0] !== id) {
arr[arr.length - 1].unshift(id)
}
if (val.children[i].children) {
children(val.children[i], id)
arr[arr.length - 1].splice(0, 1);
} else {
arr[arr.length - 1].push(val.children[i].id);
arr.push([])
}
}
return arr;
}
function searchFn(arr) {
arr.map(res => {
if (res.toString().indexOf(value) !== -1) {
searchArr = res;
}
})
return searchArr
}
return searchFn(parent.call(this, list));
}
fn(value) // 输出 [1， 11， 112]
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 fn = (value, list) => {
let res = [];
const loop = (data, temp = []) => {
for (item of data) {
if (item.id === value)
res = [...temp, item.id];
else {
if (item.children)
loop(item.children, [...temp, item.id]);
}
}
}
loop(list);
return res;
}
fn('112', data); // ["1", "11", "112"]
const findParent = (arr, idValue) => { const recursion = function(arr, index, parent) { const { child, id } = arr[index]; if (id == idValue) { let chain = parent + "," + id; chain = chain.substr(1, chain.length - 1); console.log("找到了", chain); return true; } if (child && recursion(child, 0, parent + "," + id)) { return true; } if (++index && arr.length > index && recursion(arr, index, parent)) { return true; } return false; }; recursion(arr, 0, ""); }; findParent(myArr, 232); findParent(myArr, 41); findParent(myArr, 13);
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 fn = (value, list) => { let res = []; const loop = (data, temp = []) => { for (item of data) { if (item.id === value) res = [...temp, item.id]; else { if (item.children) loop(item.children, [...temp, item.id]); } } } loop(list); return res; } fn('112', data); // ["1", "11", "112"]
大佬 加个break 感觉好点
const findParent1 = (myArr, idValue) => {
let res;
const recursion1 = function(myArr, temp = []) {
for (let item of myArr) {
if (res) break;
const { id, child } = item;
if (id == idValue) {
res = [...temp, id];
break;
}
if (child) {
recursion1(child, [...temp, id]);
}
}
};
recursion1(myArr, []);
return res;
};
findParent1(myArr, 11);
// 原始 list 如下 let arr = [ { id: 1, name: "广东", children: [ { id: 11, name: "深圳市", children: [ { id: 111, name: "南山区" }, { id: 112, name: "福田区" } ] }, { id: 12, name: "广州市", children: [ { id: 121, name: "xxx" }, { id: 122, name: "aaa" } ] }, { id: 13, name: "广州市2", children: [ { id: 131, name: "xxx2" }, { id: 132, name: "aaa2" } ] } ] } ]; let solve = function (arr,list) { for(let item of list){ arr.push({ id: item.id, name: item.name, parentId: item.parentId }); if (item.children) { solve(arr,item.children) } } return arr }
let find = function (list,id) {
let obj = list.reduce(function (a,b) {
a[b.id] = b
return a
},{});
let rr = [];
let fn = function (id) {
rr.push(id)
if (obj[id].parentId!==0) {
fn(obj[id].parentId);
}
}
fn(id)
return rr
}
console.log( find(solve([],arr),8))
const value = '112'
const list = [
{
id: '1',
children: [
{
id: '11',
children: [{
id: '111'
},{
id: '112'
}]
}
]
},
{
id: '2',
children: [
{
id: '112'
}
]
}
]
const fn = (value) => {
// 获取所有的路径
let res = []
const innerFunc = (node ,arr) => {
arr.push(node.id)
if (node.id === value) {
res.push(arr)
}
if (node.children) {
for (let i = 0; i < node.children.length; i++) {
innerFunc(node.children[i], arr.slice())
}
}
}
for (let i = 0 ; i < list.length; i++) {
innerFunc(list[i], [])
}
return res
}
fn('112')
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: 'test2',
children: [
{
id: '112',
name: 'test112'
}
]
}
]
const value = '112'
const fn = (value) => {
let tree = []
/**
* |----1----|----2----|----3----|
* =push=> =push=> =push=>
* <=pop= <=pop= <=pop=
*/
function find (arr, value) {
for (let i = 0; i < arr.length; i++) {
const e = arr[i];
const id = e.id
if (id === value) {
tree.push(id)
console.log(tree)
break
} else {
if (e.children) {
tree.push(id)
find(e.children, value)
// 判断子级是否有，有则中断父级
if (tree.includes(value)) break
}
// 退出当前的层级
if (i + 1 === arr.length) tree.pop()
}
}
}
find(data, value)
console.log(tree)
}
fn(value) // 输出 [1， 11， 112]
function getUrl(data, split = '') {
let map = {}
map = data.reduce(function (res, item) {
if (item.children) {
res = Object.assign(res, getUrl(item.children, split ? (split + ',' + item.id) : item.id))
}
item.url = split ? (split + ',' + item.id) : item.id;
res[item.id] = item;
return res
}, {})
return map
}
function find(data, val) {
return getUrl(data)[val]['url']
}
console.log(find(data,'112'))
const data = [
{
id: 1,
children: [
{
id: 2,
children: [
{
id: 3,
},
{
id: 4,
},
],
},
],
},
];
// 思路：递归遍历，找到目标id后逐级将id返回
function find(id) {
function each(items) {
for (let item of items) {
if (item.id === id) {
return [id];
}
if (item.children && item.children.length) {
const r = each(item.children);
if (Array.isArray(r)) {
r.unshift(item.id);
return r;
}
}
}
}
return each(data);
}
console.log(find(1)); // [1]
console.log(find(2)); // [1, 2]
console.log(find(3)); // [1, 2, 3]
console.log(find(4)); // [1, 2, 4]
const fn_12 = (value) => { const data = [ { id: 1, children: [ { id: 11, children: [ { id: 111 }, { id: 112 } ] } ] }, { id:2, children:[ { id:22, children:[{ id:222 }] }, { id:223, children:[ { id:2233, children:[ { id:223323 } ] }, { id:22334 } ] } ] } ] const fn_2 = (arr, ids) => arr.map((item) => { item.parentId = [...ids]; item.id === value && console.log(item.parentId); item.hasOwnProperty("children") && fn_2(item.children, [...item.parentId, item.id]); return item; }) fn_2(data,[]) } fn_12(223323)
function findAncestors(value, list) {
function find(list) {
for (let i = 0; i < list.length; i++) {
const item = list[i]
let childrenId
if (item.id === value) {
return [item.id]
} else if (item.children && (childrenId = find(item.children))) {
return [item.id].concat(childrenId)
}
}
}
return find(list)
}
const findTransIdToChildren = (data, id) => {
let arr = null
const find = (data, idArr = []) => {
if (arr) return
for (let i = 0; i < data.length; i++) {
if (arr) return
let inarr = idArr.concat(data[i].id)
if (data[i].id === id) {
arr = inarr
finded = true
return arr
}
if (data[i].children) {
find(data[i].children, inarr)
}
}
}
find(data, [])
return arr
}
const findIds = (id, data) => {
if (!findIds.ids) findIds.ids = []
for (let item of data) {
if (id === item.id) {
findIds.ids.push(id)
return findIds.ids
}
if (item.children && findIds(id, item.children).length) {
findIds.ids.unshift(item.id)
return findIds.ids
}
}
return findIds.ids
}
就不能有个正常点的？
const path = [];
function search(arr, val) {
for (let i = 0; i < arr.length; i++) {
path.push(arr[i].id);
if (arr[i].id === val) {
path.push(arr[i].id);
return true;
}
if (arr[i].child) {
if (search(arr[i].child, val) !== true) {
path.pop();
}
}
}
}
search(arr, 112);
var log = console.log;
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 res = []
function findVal(arr = [], val) {
const len = arr.length
for (let i = 0; i < len; i++) {
if (arr[i].id == val || findVal(arr[i].children, val)) {
res.push(arr[i].id)
return true
}
}
return false
}
findVal(data, '112')
log(res.reverse())
需要查找的值为value,arr为原数组
// 需要查找的值
const value = '212';
// 返回的值
let rel = []
let val = fn(value, arr, order = []);
function fn(value, arr, order) {
for (let i = 0; i < arr.length; i++) {
// 每次加入之前移除相邻节点
order = order.filter(item => {
return !new Set(arr.filter(item =>{return item.id != arr[i].id}).map(item => item.id)).has(item)
})
// 清空节点之后加入新节点
order.push(arr[i].id)
// 没找到继续查找
if (arr[i].id != value) {
if (arr[i].children) {
fn(value, arr[i].children, order)
}
} else {
rel = [...order];
}
}
return rel;
}
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 相等的值
let hasEqual = false
const findParentList = (arr, targetId, result = []) => {
for (let item of arr) {
result.push(item.id)
if (Array.isArray(item.children)) {
findParentList(item.children, targetId, result)
}
if (!hasEqual) {
tail = result.pop()
}
if (tail === targetId) {
hasEqual = true
return result
}
}
}
let r = findParentList(data, '121', [])
console.log('r: ', r)
来个不一样的, 先把树形数据扁平化, 再查找
// 扁平化数据
function getFlatData (data = [], flatData = {}, parentId) {
data.forEach((item) => {
const { children, ...rest } = item;
flatData[item.id] = { ...rest, parentId };
if (children) {
getFlatData(children, flatData, item.id);
}
});
return flatData;
}
// 找到parentId
function findParentIds (id, data) {
const flatData = getFlatData(data);
const curData = flatData[id] || {};
const result = [id];
let { parentId } = curData;
while (parentId) {
const parentNode = flatData[parentId] || {};
result.unshift(parentId);
parentId = parentNode.parentId;
}
return result;
}
const value = '112'
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 fn = (value) => {
return find(data)
function find(nodes) {
if (!Array.isArray(nodes) || !nodes.length) {
return
}
for (const node of nodes) {
if (node.id === value) {
return [node.id]
}
const r = find(node.children)
if (r) {
return [node.id, ...r]
}
}
}
}
console.log(fn(value))// 输出 [1， 11， 112]
const data = [ {id: 5}, { id: 1, name: '广东省', children: [ { id: 11, name: '深证市', children: [ { id: 111, name: '南山区', children: [ {id: 1111} ] }, { id: 112, name: '福田区' }, ] }, { id: 12, children: [ {id: 13} ] } ] } ]
const fn = (value) => {
let list = []
const findItem = (children, arr) => {
for (const item of children) {
let newArr = [...arr]
if (item.id === value) {
list.push(...newArr,value)
}
if (list.length)
return false
if (item.children) {
newArr.push(item.id)
findItem(item.children, newArr)
}
}
}
findItem(data, list)
return list
}
console.log(fn(1111)) // [1,11,111,1111]
function findParentsNode (data, id, arr = []) {
if (!data || !id) return false
for (let i = 0; i < data.length; i++) {
let nodes = arr.concat([])
nodes.push(data[i].id)
if (data[i].id === id) {
return nodes
}
if (data[i].children) {
let res = findParentsNode(data[i].children || [], id, nodes)
if (Array.isArray(res)) return res
}
}
}
function findId(data, value) {
let ret = []
function loop(data, temp = []) {
for (let i = 0; i < data.length; i++) {
if (data[i].id !== value) {
if(data[i].children&&data[i].children.length){
temp.push(data[i].id)
loop(data[i].children,temp)
temp.pop(data[i].id)
}
} else {
temp.push(data[i].id)
ret = temp.slice()
throw "已找到..."
}
}
}
try {
loop(data)
} catch (error) {
}
return ret
}
function grepObj(){
let arr = [];
return function grepRObj(obj,id){
if(id == obj.id){
return id
}else{
arr.push(obj.id);
(obj.children || []).forEach(item=>{
let _id = grepRObj.call(this,item,id);
if(_id){
arr.push(_id);
console.log('arr => ',arr);
}
arr.pop();
})
}
}
}
let fn = grepObj();
fn({
id: '1',
children: [{
id: '11',
children: [{
id: '110',
children:[{
id:"1120"
}]
}, {
id: '112'
}]
}, {
id: '12',
children: [{
id: '1120'
}, {
id: '111'
}]
}]
},1120)
/***
* 思路：
* 此题可对应 树-值为x的所有祖先
* 本质是从根节点遍历到目标节点，记录路径的问题
* 实现：
* 后序遍历，弹栈的时候前插根节点
* 时间复杂度：O(n) 空间O(n) 改为后序遍历的迭代实现的话空间可降至O(1)
*/
function fn(arr, targetId) {
let result = [];
let popRoot = false;
fnCall(arr);
return result;
function fnCall(nodeArr) {
if (!nodeArr || nodeArr.length === 0) return;
for (let node of nodeArr) {
if (node.id === targetId) {
popRoot = true;
}
// 使用popRoot 为了不再继续向下递归 只要在某个结点找到了x值整个递归程序开启回溯模式 所以使用全局flag控制
!popRoot && node.children && fnCall(node.children);
popRoot && result.unshift(node.id);
}
}
}
更多数据结构经典题可移步https://github.com/EmilyYoung71415/StructuresandAlgorithms-Code ^.^ 求star 求交流
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 }为什么运行结果不对
代码有点问题，dfs中的return放到if里面就好了
// 已知数据格式，实现一个函数 fn 找出链条中所有的父级 id
let list = [
{
id: 1,
children: [
{
id: 2,
children: [
{
id: 4,
},
{
id: 112,
children: [
{
id: 113,
},
],
},
],
},
{
id: 3,
children: [
{
id: 6,
},
{
id: 7,
children: [
{
id: 115,
},
],
},
],
},
],
},
];
function p(data, key) {
let arr = [];
function _m(_arr, _key) {
let _saveL = [];
let _index = null;
let _s = _arr.find((el, index) => {
if (el.children) {
el.children.forEach((element) => {
element.parentid = index;
});
_saveL.push(...el.children);
}
if (el.id == _key) {
_index = index;
return true;
}
});
if (!_s) {
let obj = _m(_saveL, key);
arr.unshift(_arr[obj].id);
return _arr[obj].parentid;
}
arr.push(_s.id);
return _s.parentid;
}
_m(data, key);
return arr;
}
let a = p(list, '115');
console.log(a);
const obj = [{ id: '1', name: '广东省', children: [{ id: '11', name: '深圳市', children: [{ id: '111', name: '南山区' }, { id: '112', name: '福田区' }] }] }]
const getIds = (obj, id) => {
const dfs = (obj, stack = []) => {
for(let item of obj) {
stack.push(item);
if (item.id === id) {
return stack;
} else {
if (item.children && item.children.length) {
return dfs(item.children, stack);
} else {
stack.pop(item);
}
}
}
}
return dfs(obj).map(item => item.id);
}
console.log(getIds(obj, '112'));
深度优先遍历，遍历的时候得到每个node的父ids，最后再遍历一次拿到父 ids
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 fn(parentId, nodeList) {
let nodes = []
if(nodeList) {
nodeList.forEach(node => {
nodes.push({
name: node.name,
id: node.id,
parentId: parentId
})
if(node.children) {
const pId = parentId ? parentId + '-'+ node.id : node.id
nodes = nodes.concat(fn(pId, node.children))
}
})
}
return nodes
}
function find(value) {
const nodes = fn(null, data)
const currentNode = nodes.find(item => item.id === value)
const ids = [...currentNode.parentId.split('-'), currentNode.id]
console.log(ids)
}
find('121')
function findIds(list, value) {
return dfs(list, value);
}
function dfs(list, value) {
const stack = [...list];
while (stack.length) {
const cur = stack.pop();
// 找到目标节点，递归结束
if (cur.id === value) {
return [cur.id];
} else if (cur.children && cur.children.length) {
const res = dfs(cur.children, value);
if (res) {
return [cur.id, ...res]
}
}
}
}
const value = '112';
console.log(findIds(data, 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'
}
]
}
]
}];
const fn = (data,vule)=>{
let res = []
const dfs = (arr,temp = []) =>{
for(const node of arr){
if(node.id === vule){
// 如果该节点就是
temp.push(node.id)
res = temp
return
}else{
// 继续搜索
if(node.children){
dfs(node.children,temp.concat(node.id))
}
}
}
}
dfs(data)
return res
}
console.log(fn(data,'11'))
var list = [{
id: '1',
children: [{
id: '11',
children: [{
id: '111'
}, {
id: '112'
}]
}, {
id: '12',
children: [{
id: '121'
}, {
id: '122'
}]
}]
}]
const res = [];
function find(list, value, parent) {
for (let i = 0; i < list.length; i++) {
if (parent) {
list[i].parent = parent;
}
if (list[i].id === value) {
let p = list[i];
while (p) {
res.push(p.id);
p = p.parent;
}
break;
}
if (list[i].children) {
find(list[i].children, value, list[i])
}
}
}
const value = '121';
find(list, value)
console.log(res.reverse())
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 fn(id, arr) {
let target = []
function rfn(finArr, cArr = []) {
let newArr = [...cArr]
if (finArr instanceof Array) {
finArr.find(item => {
if (item.id === id) {
target = [...newArr, item.id]
return true
} else {
if (item.children) {
rfn(item.children, [...newArr, item.id])
if (target.length > 0) {
return true
}
} else {
return false
}
}
})
}
}
rfn(arr)
return target
}
console.log(fn('112', data));
不知道这样可以不
思路是每次遍历之前都利用结构记录一下层级，如果知道对应的id，直接返回即可
var searched = [];
var stack = [];
var has = false;
var id = '24';
function DFS(arr) {
//深度遍历
if (isEnd(arr)) {
if (arr.id == id) {
return true;
} else {
stack.pop();
}
}
for (var i = 0; i < arr.child.length; i++) {
var node = arr.child[i];
if (has) {
break;
}
if (!searched.includes(node.id)) {
searched.push(node.id);
stack.push(node.id);
if (DFS(node)) {
has = true;
return stack;
}
}
}
return stack;
}
function isEnd(arr) {
if (!arr.child || arr.id == id) {
return true;
}
}
`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++ }
return res
} console.log(fn(value, list))`
广度优先遍历
@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 }
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 findId(list) {
let arr = []
list.map(item => {
arr.push(item.id)
item.children && arr.push(findId(item.children))
})
return arr.flat(10)
}
function fnBFS(list, target) { let resMap = {}
let queue = []
let map = {}
list.forEach(item => {
queue.push(item)
map[item.id] = true
})
while(queue.length) {
let item = queue.shift()
if(item.children) {
for(child of item?.children) {
if(!map[child.id]) {
queue.push(child)
map[child.id] = true
resMap[child.id] = item.id
}
}
}
}
console.log(resMap)
let res = ''
while(resMap[target]) {
res += ${target} ->
target = resMap[target]
if(!resMap[target]) {
res += target
}
}
console.log(res) }
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'
}]
}]
}]
//递归+some（匹配到值结束）
function findIdList(data,id,parent) {
const has = data.some(item=>{
item.value = parent?[...parent.value,item.id]:[item.id]
if(item.id === id){
findIdList.value = item.value
return true
}
if(item.children){
return findIdList(item.children,id,item)
}
})
if(has){
return findIdList.value
}
}
const result = findIdList(data,"222")
console.log(result);
前缀树 Trie，复杂度仅为需要查找value的长度：
class Node {
constructor(isWord = false) {
this.isWord = isWord;
this.next = new Map();
}
}
class Trie {
constructor() {
this.root = new Node();
}
add(key) {
let cur = this.root;
for (let i = 0; i < key.length; i++) {
const c = key[i];
if (!cur.next.get(c)) {
cur.next.set(c, new Node());
}
cur = cur.next.get(c);
}
}
match(prefix) {
if (prefix === "") {
return [];
}
let cur = this.root;
const res = [];
for (let i = 0; i < prefix.length; i++) {
const c = prefix[i];
if (!cur.next.get(c)) {
return [];
}
res.push(prefix.slice(0, i + 1));
cur = cur.next.get(c);
}
return res;
}
}
const trie = new Trie();
function add(address) {
for (let i = 0; i < address.length; i++) {
trie.add(address[i].id);
if (address[i].children) {
add(address[i].children);
}
}
}
add(address);
trie.match("112"); // [1,11,112]
trie.match("111"); // [1,11,111]
trie.match("11"); // [1,11]
trie.match("110"); // []
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) {
const result = [];
for(let i = 0; i < arr.length; i++) {
const item = arr[i];
if(item.id === value) {
return [value]
}
if(item.children) {
const ids = find(item.children, value);
if(ids.length > 0) {
result.push(item.id, ...ids);
}
}
}
return result;
}
console.log(find(data, '11'));
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'))
