前端演演算法leetcode109題解有序連結串列轉換二元搜尋樹

2022-09-26 14:05:21

題目

題目地址

給定一個單連結串列的頭節點 head ，其中的元素 按升序排序 ，將其轉換為高度平衡的二元搜尋樹。

本題中，一個高度平衡二元樹是指一個二元樹每個節點的左右兩個子樹的高度差不超過 1。

範例 1:

輸入: head = [-10,-3,0,5,9]

輸出: [0,-3,9,-10,null,5]

解釋: 一個可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二元搜尋樹。

範例 2:

輸入: head = []

輸出: []

提示:

head 中的節點數在[0, 2 * 104] 範圍內
-105 <= Node.val <= 105

解題思路-基礎

本題要求我們將給定的有序連結串列轉為高度平衡的二元搜尋樹，所以我們要保證每個子樹的左子樹的值都比它小，右子樹的值都比它大，同時高度差不超過1。

因為給定的連結串列是升序的，所以我們遍歷連結串列節點將節點值存入陣列，這樣就得到了一個升序的陣列。然後取陣列的中間節點為根節點的值，左邊的都是小於它的值，右邊的都是大於它的值，再通過左右兩邊的數值去構造當前節點的左右子樹。最後當所有值都處理完，就構造完成了一顆高度平衡的二元搜尋樹。

程式碼實現

var sortedListToBST = function(head) {
  if(head === null){
      return null
  }
  const list = []
  while(head){
      list.push(head.val)
      head = head.next
  }
  function buildTree(list){
      const len = list.length
      if(len===0){
          return null
      }
      const mid = len>>1
      const nodeVal = list[mid]
      const l = list.slice(0,mid)
      const r = list.slice(mid+1)
      return new TreeNode(nodeVal,buildTree(l),buildTree(r))
  }
  return buildTree(list)
};

解題思路-優化

上面的實現中我們每次都要切割 list 陣列，其實可以更換為記錄左右下標的方式，即省去了切割陣列的過程，又不用每次建立子陣列。

程式碼實現

var sortedListToBST = function(head) {
  if(head === null){
      return null
  }
  const list = []
  while(head){
      list.push(head.val)
      head = head.next
  }
  function buildTree(l,r){
      if(l>r){
          return null
      }
      const mid = (l+r)>>1
      const nodeVal = list[mid]
      return new TreeNode(nodeVal,buildTree(l,mid-1),buildTree(mid+1,r))
  }
  return buildTree(0,list.length-1)
};

解題思路-進階

上面的實現方式時、空複雜度都是 O(nlogn) O(logn)，但是第二種做了進一步優化，實際表現會更好一點。而下面的實現方式時、空複雜度為：O(n) O(logn)。

這裡我們轉換思路，不去首先構造根節點，而是採用中序遍歷的順序構造目標二元樹，這樣構造的順序就可以和遍歷連結串列的順序吻合，達到在遍歷連結串列的過程完成構造二元樹。

程式碼實現

const sortedListToBST = (head) => {
    if (head == null){
        return null
    }
    let len = 0
    let cur = head
    while (head) {
        len++
        head = head.next
    }
    function buildTree(l,r){
        if (l > r){
            return null
        }
        const mid = (l + r) >>> 1
        const leftTree = buildTree(l, mid - 1)
        const node = new TreeNode(cur.val)
        node.left = leftTree
        cur = cur.next           
        node.right = buildTree(mid + 1, r)
        return node
  }
  return buildTree(0, len - 1)
};

至此我們就完成了 leetcode-109-有序連結串列轉換二元搜尋樹，更多關於前端演演算法有序連結串列轉換二元搜尋樹的資料請關注it145.com其它相關文章！

前端演演算法leetcode109題解有序連結串列轉換二元搜尋樹

目錄

題目

解題思路-基礎

程式碼實現

解題思路-優化

程式碼實現

解題思路-進階

程式碼實現

熱門文章