The day before yesterday, I met a topic of multi-fork tree interview.

Question: A tree of data (the following data), the interviewer give you an ID, and then get the corresponding name?

The data structure looks something like this

var cityData = [
      {
        id: 1,
        name: 'Guangdong',
        children: [
          {
            id: 11,
            name: 'shenzhen',
            children: [
              {
                id: 111,
                name: 'the baoan,
                children: [
                  {
                    id: 1111,
                    name: 'from the',
                    children:[
                      {
                        id: 11111,
                        name: 'peng chau',
                        children:[]
                      },
                      {
                        id: 11112,
                        name: 'the ganoderma lucidum',
                        children:[]
                      }
                    ]
                  },
                  {
                    id: 1112,
                    name: 'nan shan',
                    children:[
                      {
                        id: 11121,
                        name: 'Science Park',
                        children:[]
                      }
                    ]
                  }
                ]
              },
              {
                id: 112,
                name: '福田',
                children: []
              }
            ]
          },
          {
            id: 12,
            name: 'guangzhou',
            children: [
              {
                id: 122,
                name: 'Baiyun District',
                children: [
                  {
                    id: 1222,
                    name: 'Baiyun District',
                    children: []
                  }
                ]
              },
              {
                id: 122,
                name: 'Pearl Sea',
                children: []
              }
            ]
          }
        ]
      },
      {
        id: 2,
        name: 'Hunan',
        children: []
      }
    ];
Copy the code

For example, if I want name with ID 11112 to return ganoderma lucidum, how many solutions do you have?

Recursive method

This problem shows you that this is the way to recurse, and the code is as follows


let result = ' 'Const recursion = (cityData, id) => {const recursion = (cityData, id) =>if(! cityData || ! cityData.length)return; // General loop cityDatafor (leti = 0, len = cityData.length; i < len; i++) { const childs = cityData[i].children; // If id is matched, this is the result we wantif(cityData[I].id === id) {result = cityData[I].name} // If there are children, perform recursionif(childs && childs.length > 0){ recursion(childs, id); }}returnresult }; const r = recursion(cityData, 11112); The console. The log (r) / / ganoderma lucidumCopy the code

Oyes ~~~ finished?? The interviewer may not be satisfied, but there are several solutions

Breadth-first implementation

let result = ' '

const range = (cityData, id) => {
  if(! cityData || ! cityData.length)return; // Define a data stacklet stack = [];

  letitem = null; // Put the first tier node on the stackfor (var i = 0, len = cityData.length; i < len; i++) {
    stack.push(cityData[i]);
  }

  while(stack.length) {// Remove the first item of the stack item = stack.shift(); // Assign to result if it matchesif(item.id === id) {result = item.name} // If this node has children, continue to add to the bottom of the stackif(item.children && item.children.length) { stack = stack.concat(item.children); }}return result
};

letr1 = range(cityData, 11112); The console. The log (r1) / / ganoderma lucidumCopy the code

Depth-first implementation

let result = ' 'Const deep = (cityData, id) => {// No data is returnedif(! cityData || ! cityData.length)return; // Define a data stacklet stack = []
  letItem = null // Add layer 1 node to data stack firstfor(var i = 0, len = cityData.length; i < len; I ++) {stack.push(cityData[I])} // loopwhile (stack.length) {
    item = stack.shift()
    if(item.id === id) {result = item.name} // If this node has children, continue to add to the top of the stackif(item.children && item.children. Length) {stack = item.children. Concat (stack); }}return result
};

letR3 = deep(cityData, 11112) console.log(r3) // ReishiCopy the code

Regular implementation

Const regular = (cityData, id) => {// No data is returnedif(! cityData || ! cityData.length)return; // Data is converted to a stringletCityStr = json.stringify (cityData) // Define the relet reg = new RegExp(`"id":${id}."name":"([^\\x00-\\xff]+)", ') // takes a substring of the re and returns itreturn (cityStr.match(reg))[1]
}

letr4 = regular(cityData, 11112); The console. The log (r4) / / ganoderma lucidumCopy the code

Here are 4 ways, there should be many other ways, if you have a message to me, thank you ~~

Amway blog ~~~github.com/naihe138/na…