高級前端面試手寫扁平數據結構轉Tree

Posted on by

前言

招聘季節一般都在金三銀四，或者金九銀十。最近在這五六月份，陸陸續續面試瞭十幾個高級前端。有一套考察算法的小題目。後臺返回一個扁平的數據結構，轉成樹。

我們看下題目：打平的數據內容如下：

let arr = [
    {id: 1, name: '部門1', pid: 0},
    {id: 2, name: '部門2', pid: 1},
    {id: 3, name: '部門3', pid: 1},
    {id: 4, name: '部門4', pid: 3},
    {id: 5, name: '部門5', pid: 4},
]

輸出結果

[
    {
        "id": 1,
        "name": "部門1",
        "pid": 0,
        "children": [
            {
                "id": 2,
                "name": "部門2",
                "pid": 1,
                "children": []
            },
            {
                "id": 3,
                "name": "部門3",
                "pid": 1,
                "children": [
                    // 結果 ,,,
                ]
            }
        ]
    }
]

我們的要求很簡單，可以先不用考慮性能問題。實現功能即可，回頭分析瞭面試的情況，結果使我大吃一驚。

10%的人沒思路，沒碰到過這種結構

60%的人說用過遞歸，有思路，給他個筆記本，但就是寫不出來

20%的人在引導下，磕磕絆絆能寫出來

剩下10%的人能寫出來，但性能不是最佳

感覺不是在招聘季節遇到一個合適的人真的很難。

接下來，我們用幾種方法來實現這個小算法

什麼是好算法，什麼是壞算法

判斷一個算法的好壞，一般從執行時間和占用空間來看,執行時間越短，占用的內存空間越小，那麼它就是好的算法。對應的，我們常常用時間復雜度代表執行時間，空間復雜度代表占用的內存空間。

時間復雜度

時間復雜度的計算並不是計算程序具體運行的時間，而是算法執行語句的次數。

隨著n的不斷增大，時間復雜度不斷增大，算法花費時間越多。 常見的時間復雜度有

  • 常數階O(1)
  • 對數階O(log2 n)
  • 線性階O(n)
  • 線性對數階O(n log2 n)
  • 平方階O(n^2)
  • 立方階O(n^3)
  • k次方階O(n^K)
  • 指數階O(2^n)

計算方法

  • 選取相對增長最高的項
  • 最高項系數是都化為1
  • 若是常數的話用O(1)表示

舉個例子：如f(n)=3*n^4+3n+300 則 O(n)=n^4

通常我們計算時間復雜度都是計算最壞情況。計算時間復雜度的要註意的幾個點

  • 如果算法的執行時間不隨n的增加而增長，假如算法中有上千條語句，執行時間也不過是一個較大的常數。此類算法的時間復雜度是O(1)。 舉例如下：代碼執行100次，是一個常數，復雜度也是O(1)。
    let x = 1;
    while (x <100) {
     x++;
    }
  • 有多個循環語句時候，算法的時間復雜度是由嵌套層數最多的循環語句中最內層語句的方法決定的。舉例如下：在下面for循環當中，外層循環每執行一次，內層循環要執行n次，執行次數是根據n所決定的，時間復雜度是O(n^2)。
  for (i = 0; i < n; i++){
         for (j = 0; j < n; j++) {
             // ...code
         }
     }
  • 循環不僅與n有關，還與執行循環判斷條件有關。舉例如下：在代碼中，如果arr[i]不等於1的話，時間復雜度是O(n)。如果arr[i]等於1的話，循環不執行，時間復雜度是O(0)。
    for(var i = 0; i<n && arr[i] !=1; i++) {
    // ...code
    }

空間復雜度

空間復雜度是對一個算法在運行過程中臨時占用存儲空間的大小。

計算方法：

  • 忽略常數，用O(1)表示
  • 遞歸算法的空間復雜度=(遞歸深度n)*(每次遞歸所要的輔助空間)

計算空間復雜度的簡單幾點

僅僅隻復制單個變量，空間復雜度為O(1)。舉例如下：空間復雜度為O(n) = O(1)。

   let a = 1;
   let b = 2;
   let c = 3;
   console.log('輸出a,b,c', a, b, c);

遞歸實現，調用fun函數，每次都創建1個變量k。調用n次，空間復雜度O(n*1) = O(n)。

    function fun(n) {
       let k = 10;
       if (n == k) {
           return n;
       } else {
           return fun(++n)
       }
    }

不考慮性能實現，遞歸遍歷查找

主要思路是提供一個遞getChildren的方法，該方法遞歸去查找子集。 就這樣，不用考慮性能，無腦去查，大多數人隻知道遞歸，就是寫不出來。。。

/**
 * 遞歸查找，獲取children
 */
const getChildren = (data, result, pid) => {
  for (const item of data) {
    if (item.pid === pid) {
      const newItem = {...item, children: []};
      result.push(newItem);
      getChildren(data, newItem.children, item.id);
    }
  }
}
/**
* 轉換方法
*/
const arrayToTree = (data, pid) => {
  const result = [];
  getChildren(data, result, pid)
  return result;
}

從上面的代碼我們分析，該實現的時間復雜度為O(2^n)。

不用遞歸，也能搞定

主要思路是先把數據轉成Map去存儲，之後遍歷的同時借助對象的引用，直接從Map找對應的數據做存儲

function arrayToTree(items) {
  const result = [];   // 存放結果集
  const itemMap = {};  // 
  // 先轉成map存儲
  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;
}

從上面的代碼我們分析，有兩次循環，該實現的時間復雜度為O(2n)，需要一個Map把數據存儲起來，空間復雜度O(n)

最優性能

主要思路也是先把數據轉成Map去存儲，之後遍歷的同時借助對象的引用，直接從Map找對應的數據做存儲。不同點在遍歷的時候即做Map存儲,有找對應關系。性能會更好。

function arrayToTree(items) {
  const result = [];   // 存放結果集
  const itemMap = {};  // 
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;
    if (!itemMap[id]) {
      itemMap[id] = {
        children: [],
      }
    }
    itemMap[id] = {
      ...item,
      children: itemMap[id]['children']
    }
    const treeItem =  itemMap[id];
    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      itemMap[pid].children.push(treeItem)
    }
  }
  return result;
}

從上面的代碼我們分析，一次循環就搞定瞭，該實現的時間復雜度為O(n)，需要一個Map把數據存儲起來，空間復雜度O(n)

小試牛刀

方法 1000(條) 10000(條） 20000(條） 50000(條)
遞歸實現 154.596ms 1.678s 7.152s 75.412s
不用遞歸，兩次遍歷 0.793ms 16.499ms 45.581ms 97.373ms
不用遞歸，一次遍歷 0.639ms 6.397ms 25.436ms 44.719ms

從我們的測試結果來看，隨著數量的增大，遞歸的實現會越來越慢，基本成指數的增長方式。

以上就是高級前端面試手寫扁平數據結構轉Tree的詳細內容，更多關於扁平數據結構轉Tree的資料請關註WalkonNet其它相關文章！

推薦閱讀：