前天面试遇到一个多叉树面试的题目, 在这里分享记录一下.
题目: 一个树形的数据 (如下数据), 面试官给你一个 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://juejin.im/post/5ad178135188255569196a72