用一題 JS題測驗你是前二十趴的工程師還是後七十趴的工程師！

5 min readNov 8, 2022

會寫這篇文章是看到前端論壇裡面的這篇文章面试了十几个高级前端，竟然连（扁平数据结构转Tree）都写不出来。看到他聳動的標題，頓時就讓我對內容產生了興趣。文章內容在說這個題目，作者給來面試的高級前端測試，結果70趴的人寫不出來，20趴的人要經過引導才寫得出來，剩下十趴寫的出來但是效能不好。那我們就來看看題目吧，看看你是不是那百分之十的人吧！

這個題目是長這樣的，給你一個稱為arr的input，把它轉換成樹狀格式。

回傳的樹狀格式應該要長類似以下這樣：

[  {    "id": 1,    "name": "部门1",    "pid": 0,    "children": [         {            "id": 2,            "name": "部门2",            "pid": 1         },         {            "id": 3,            "name": "部门3",            "pid": 1,            "children": [                 {                     "id": 4,                     "name": "部门4",                     "pid": 3,                     "children": [                         {                            "id": 5,                            "name": "部门5",                            "pid": 4                         }                      ]                  }            ]         }    ]   }]

常見的做法就是用recursive，所以這也是我最先想到的方法，但是不知怎地就是寫不出正確答案。。。後來看了文章的程式碼才瞭解了思路。讀者可以先試著回答看看，看能不能寫出答案，

用提供的array，把它轉換成樹狀結構

Follow up:

能不能用時間複雜度O(n)的程式碼回答上面的問題

用recursive來回答，因為用了for loop加上recursive，所以Big O會是O(n²)


// 扁平array結構 轉換成 json tree (recursive)
// time complexity: O(n²)function flatToTree(arr, pid) {
    let result = []
    for(let i=0; i< arr.length;i++) {
        if (arr[i].pid === pid) {
            let children = flatToTree(arr, arr[i].id)
        if (children.length) {
                arr[i].children = children
            }
            result.push(arr[i])
        }
    }
    return result
}

follow up的部分，可以用Object來實作，Big O會是O(n)

// 扁平array結構 轉換成 json tree (object)
// time complexity: O(n)function arrayToTree(items) {
  const result = [];   
  const itemMap = {};   
    
  for (const item of items) {
    itemMap[item.id] = {...item, children: []}
  }
  
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;
    const treeItem =  itemMap[id];
    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      itemMap[pid].children.push(treeItem)
    }}
  return result;
}

如果上面兩題你都答的出來(恭喜你是前二十趴的人！)，或是還是覺得意猶未竟，那下面還有兩題可以試試看。

承前面的題目，用上面給予的arr，寫出一個function，在輸入子節點 id後，回傳子節點的資料

function findChild(targetId, tree) {
  if (!tree.length) return
  for (let i = 0; i < tree.length; i++) {
   if (tree[i].id === targetId) {
    return tree[i]
   } else {
    if (tree[i]?.children?.length) {
     let childNode = findChild(targetId, tree[i].children)
     if (childNode) return childNode
    }
   }
  }
 }

2. 承前面的題目，用上面給予的arr，寫出一個function，根據子節點id找到父節點集合

function getParents(treeData, targetId) {
    let result = []
    let callback = (data, targetId) => {
        if (!data || !Array.isArray(data)) {
            return 
        }for(const i in data) {
            if (data[i].id === targetId) {
                result.unshift(data[i].id)
                callback(treeData, data[i].pid)
            }
            if (data[i].children && Array.isArray(data[i].children)) {
                callback(data[i].children, targetId)
            }
        }
    }
    callback(treeData, targetId)
    return result
}

以上就是我今天看到的有趣的題目，如果寫不出來也不要氣餒（我第一次寫沒寫出來。。。太丟臉了）所謂失敗乃成功之母，這次的失敗相信會是未來繼續進步的養分的！

Resources:

https://juejin.cn/post/6983904373508145189

https://blog.csdn.net/mf_717714/article/details/114367055

用一題 JS題測驗你是前二十趴的工程師還是後七十趴的工程師！

Written by water