第 92 题：已知数据格式，实现一个函数 fn 找出链条中所有的父级 id

[yygmind]

const value = '112'
const fn = (value) => {
...
}
fn(value) // 输出 [1， 11， 112]

[Zephylaci]

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

[ZodiacSyndicate]

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
}

[kungithub]

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次子节点，但是需要额外空间记录父节点引用

[sgzhm4444]

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

这个情景不太对吧

[zzzzzhowie]

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

这个情景不太对吧

嗯我再研究一下~

[Zephylaci]

@ZodiacSyndicate
这个写法想查112的时候不就查不出来了..

[lhyt]

• 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
}

[Rashomon511]

        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;
        }

[GuoYuFu123]

/*
* 已知数据格式，实现一个函数 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"]

[18692959234]

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]

写法是深度优先， 增加了数据结构的深度与广度，能可以正确输出

[lvwxx]

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
}

[B2D1]

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

[nailfar]

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

[zzzzzhowie]

评论好多直接复制黏贴都是错的，发之前先测试一下啊，另外如果按照示例中省市区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)