前天面试遇到一个多叉树面试的题目,在这里分享记录一下。
题目:一个树形的数据(如下数据),面试官给你一个id,然后拿到对应的name?
数据结构大概是这个样子
var cityData = [ { id: 1, name: "广东省", children: [ { id: 11, name: "深圳", children: [ { id: 111, name: "宝安", children: [ { id: 1111, name: "西乡", children:[ { id: 11111, name: "坪洲", children:[] }, { id: 11112, name: "灵芝", children:[] } ] }, { id: 1112, name: "南山", children:[ { id: 11121, name: "科技园", children:[] } ] } ] }, { id: 112, name: "福田", children: [] } ] }, { id: 12, name: "广州", children: [ { id: 122, name: "白云区", children: [ { id: 1222, name: "白云区", children: [] } ] }, { id: 122, name: "珠海区", children: [] } ] } ] }, { id: 2, name: "湖南省", children: [] } ];
比如说 我要id是11112的name返回是灵芝,请问你有几种解法??
递归方法这题目让人看到这不就是考用递归的方法嘛,代码如下
let result = "" // 递归实现 const recursion = (cityData, id) => { // cityData数据为空的时候直接返回 if (!cityData || !cityData.length) return; // 常规循环cityData for (let i = 0, len = cityData.length; i < len; i++) { const childs = cityData[i].children; // 如果匹配到id的话,就是我们要的结果 if (cityData[i].id === id) { result = cityData[i].name } // 如果还有子节点,执行递归 if(childs && childs.length > 0){ recursion(childs, id); } } return result }; const r = recursion(cityData, 11112); console.log(r) // 灵芝
oyes~~~完成了么??面试官可能不满意哦,下面还有几种解法
广度优先实现let result = "" const range = (cityData, id) => { if (!cityData || !cityData.length) return; // 定义一个数据栈 let stack = []; let item = null; //先将第一层节点放入栈 for (var i = 0, len = cityData.length; i < len; i++) { stack.push(cityData[i]); } while (stack.length) { // 将数据栈的第一个取出来 item = stack.shift(); // 如果符合就赋值给result if (item.id === id) { result = item.name } //如果该节点有子节点,继续添加进入栈底 if (item.children && item.children.length) { stack = stack.concat(item.children); } } return result }; let r1 = range(cityData, 11112); console.log(r1) // 灵芝深度优先实现
let result = "" const deep = (cityData, id) => { // 没有数据直接返回 if (!cityData || !cityData.length) return; // 先定义一个数据栈 let stack = [] let item = null //先将第一层节点放入数据栈 for (var i = 0, len = cityData.length; i < len; i++) { stack.push(cityData[i]) } // 循环 while (stack.length) { item = stack.shift() if (item.id === id) { result = item.name } //如果该节点有子节点,继续添加进入栈顶 if (item.children && item.children.length) { // 注意这里调换了顺序 stack = item.children.concat(stack); } } return result }; let r3 = deep(cityData, 11112) console.log(r3) // 灵芝正则方式实现
const regular = (cityData, id) => { // 没有数据直接返回 if (!cityData || !cityData.length) return; // 数据转成字符串 let cityStr = JSON.stringify(cityData) // 定义正则 let reg = new RegExp(`"id":${id},"name":"([^x00-xff]+)",`) // 取到正则的子字符串并返回 return (cityStr.match(reg))[1] } let r4 = regular(cityData, 11112); console.log(r4) // 灵芝
这里列举了4种方法,应该还有很多种方法,大佬们有的话可以留言给我,先谢谢啦~~
安利一波博客~~~https://github.com/naihe138/naice-blog
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/94220.html
简单的遍历一个树形结构数据的几种方法、非递归方法效率最好。 (function (window, undefined) { var treeNodes = [ { id: 1, name: 1, children: [ { i...
摘要:讲了一下我在电力物联网项目中通过设计的文件远程升级功能。完成聊天毕业规划怎么样收到面试调查问卷等待中。。。。。 7.31 投递提前批c++客户端岗位 8.16 被转...
摘要:多叉树的分析及实现好了,终于回到了第一篇文章提到的组织结构的多叉树实现,有了前两篇文章的基础,多叉树的实现也就变得简单了从后台拿到的原始数据形式为总部工程部工程部工程部工程部测试部测试部测试部生产部规划部市场部这是一个典型的多叉树结构,总部 js多叉树的分析及实现 好了,终于回到了第一篇文章提到的组织结构的多叉树实现,有了前两篇文章的基础,多叉树的实现也就变得简单了 从后台拿到的原始数...
阅读 3115·2021-10-27 14:20
阅读 2490·2021-10-08 10:05
阅读 1598·2021-09-09 09:33
阅读 2845·2019-08-30 13:16
阅读 1408·2019-08-29 18:34
阅读 1144·2019-08-29 10:58
阅读 1195·2019-08-28 18:22
阅读 1199·2019-08-26 13:33