每週分享第 7期：我遇到的崩潰遞迴地獄

分享本週所看到的任何事🤓。

Debby Ji

Published in

Debby’s Playground

8 min readMar 22, 2019

Table of Content

崩潰遞迴地獄

這週ㄧ樣是瘋狂面試週，想來分享一道目前印象最深的面試題，有興趣的人也可以試著解解看（？）

題目是這樣的，一個 sitemap 陣列存著網站上的選單結構，寫出一個 function ，帶入所有選單及某個選單 name 會回傳一個陣列除了包含傳入的參數 name 外還有它的所有父層 name。例如 find(sitemap, '草莓蛋糕')，會返回 ['草莓蛋糕', '蛋糕', '甜點']，注意 function 需要能符合很多層（不只目前的三層）。

完整題目如下：（如有雷同純屬巧合🙈）

const sitemap = [{
    name: '三明治',
    children: []
  },
  {
    name: '甜點',
    children: [{
        name: '蛋糕',
        children: [{
            name: '草莓蛋糕',
            children: []
          },
          {
            name: '水果蛋糕',
            children: []
          }
        ]
      },
      {
        name: '鬆餅',
        children: [{
            name: '奶油鬆餅',
            children: []
          },
          {
            name: '蜂蜜鬆餅',
            children: []
          }
        ]
      },
      {
        name: '甜甜圈',
        children: [{
            name: '原味甜甜圈',
            children: []
          }
        ]
      }
    ]
  },
  {
    name: '飲品',
    children: [{
        name: '奶茶',
        children: []
      },
      {
        name: '紅茶',
        children: []
      },
      {
        name: '拿鐵',
        children: []
      }
    ]
  }
]function find (sitemap, current) {
  // your code 
}
const current = '草莓蛋糕'
console.log(find(sitemap, '草莓蛋糕')) // ['草莓蛋糕', '蛋糕', '甜點']

當下一聽到題目，第一個念頭是覺得「似乎不難」，因為我有碰過類似的情境，只是那時用 vue 解決。總之我沒想太多的寫出答案，現在想起來很蠢，因為我是寫死只有三層可以用的 function，後來面試官才講要很多層都可以才行，也另外提示我可以使用「遞迴」，不過面試當下我還是寫不出來，於是就把題目帶回家好好想，。

最初的版本有點忘記了，這應該算是第二個版本，會這樣寫是來自面試官的提示：「先把每層的 name 都找出來，然後把 name 丟進結果，不對的話再拿出來」，總之就寫了很久，但結果還是一直不對。

let result = [];
let flag = false;function find (sitemap, current) {
  for (let i = 0; i < sitemap.length; i++) {
   if(flag) {
     return result
    }
    result.push(sitemap[i].name);
    if(sitemap[i].name === current) {
      flag = true;
    } 
    find(sitemap[i].children, current)
    if(!flag) {
     result.pop();
    }
  }
}

話不多說，直接來講最後怎麼解的好了，當然我又再一次仰賴了 Huli 老師🤣 再次感謝老師一步一步的引導，結果只有最後一小步是我自己想的😂

第一步：先只考慮第一層

function find (sitemap, current) {
  for (let i = 0; i < sitemap.length; i++) {
      const site = sitemap[i]
      if (site.name === current) {
        return [site.name] // 如果找到了，回傳自己本身
      }
  }
}

2. 然後往下找，相信他會傳給你結果（這句話聽起來很玄，不過也是因為這句才解出來的）

function find (sitemap, current) {
  for (let i = 0; i < sitemap.length; i++) {
    const site = sitemap[i]
    if (site.name === current) {
      return [site.name] // 如果找到了，回傳自己本身
    }
    
    // result 會是往下找的結果，會是一個陣列，如果找不到會是 undefined
    const result = find(site.children, current)
  }
}

3. 如果 result 有值，就把它存起來。最後這一步看似很簡單但也想了很久，最後竟然是卡在想著如何把結果存起來，完全忘記有 concat 這方法，大傻眼😱

function find (sitemap, current) {
  for (let i = 0; i < sitemap.length; i++) {
      const site = sitemap[i]
      if (site.name === current) {
        return [site.name]
      }
      const result = find(site.children, current)
      if(result) {
       return result.concat(site.name)
      }
  }
}

解完的瞬間真的想放煙火🎊 但還是覺得遞迴好難啊，想再多做幾個遞迴的題目（歡迎出題考我🤣）