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

题目：一个树形的数据(如下数据)，面试官给你一个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