前天面试遇到一个多叉树面试的题目，在这里分享记录一下。

文章转载：乐字节

题目：一个树形的数据(如下数据)，面试官给你一个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种方法，应该还有很多种方法，大佬们有的话可以留言给我，先谢谢啦~~

文章转载：乐字节

相关面试资料，可以加Java交流裙：103-339-3185 备注：75 即可 防止恶意广告