面试题：给你个id，去拿到name，多叉树遍历

Panda 发布于2019-08-05 13:31 / 1674人阅读

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

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

专线服务云服务器给你个多叉树多叉树全 python多叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/57404.html

面试题：给你个id，去拿到name，多叉树遍历

前天面试遇到一个多叉树面试的题目，在这里分享记录一下。题目：一个树形的数据(如下数据)，面试官给你一个id，然后拿到对应的name? 数据结构大概是这个样子 var cityData = [ { id: 1, name: 广东省, children: [ { id: 11, ...

jayce 2019-08-22 16:18 评论0 收藏0
❤️两万字《算法 + 数据结构》如何开始❤️

文章目录 1️⃣前言：追忆我的刷题经历2️⃣算法和数据结构的重要性?1、适用人群?2、有何作用?3、算法简介?4、数据结构 3️⃣如何开始持续的刷题?1、立军令状?‍❤️‍?2、培养兴趣?3、狂切水题??4、养成习惯?5、一周出师 4️⃣简单数据结构的掌握?1、数组?2、字符串?3、链表?4、哈希表?‍?‍?5、队列?‍?‍?‍?6、栈?7、二叉树?8、多叉树?9、森林?10、树状数组?11、...

BoYang 2021-09-14 17:57 评论0 收藏0
遍历多叉树（递归、非递归广度优先、深度优先）

简单的遍历一个树形结构数据的几种方法、非递归方法效率最好。 (function (window, undefined) { var treeNodes = [ { id: 1, name: 1, children: [ { i...

wing324 2019-08-22 10:57 评论0 收藏0
字节跳动上海DATA部门后端开发秋招面试经历

摘要：讲了一下我在电力物联网项目中通过设计的文件远程升级功能。完成聊天毕业规划怎么样收到面试调查问卷等待中。。。。。 7.31 投递提前批c++客户端岗位 8.16 被转...

Ocean 2021-09-09 09:33 评论0 收藏0
js多叉树的分析及实现

摘要：多叉树的分析及实现好了，终于回到了第一篇文章提到的组织结构的多叉树实现，有了前两篇文章的基础，多叉树的实现也就变得简单了从后台拿到的原始数据形式为总部工程部工程部工程部工程部测试部测试部测试部生产部规划部市场部这是一个典型的多叉树结构，总部 js多叉树的分析及实现好了，终于回到了第一篇文章提到的组织结构的多叉树实现，有了前两篇文章的基础，多叉树的实现也就变得简单了从后台拿到的原始数...

lucas 2019-08-20 14:05 评论0 收藏0