前端算法leetcode109題解有序鏈表轉換二叉搜索樹

更新時間：2022年09月23日 09:43:12 作者：前端_奔跑的蝸牛

這篇文章主要為大家介紹了前端算法leetcode109題解有序鏈表轉換二叉搜索樹示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

題目

題目地址

給定一個單鏈表的頭節(jié)點 head ，其中的元素 按升序排序 ，將其轉換為高度平衡的二叉搜索樹。

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

示例 1:

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

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

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

示例 2:

輸入: head = []

輸出: []

提示:

head 中的節(jié)點數(shù)在[0, 2 * 104] 范圍內(nèi)
-105 <= Node.val <= 105

解題思路-基礎

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

因為給定的鏈表是升序的，所以我們遍歷鏈表節(jié)點將節(jié)點值存入數(shù)組，這樣就得到了一個升序的數(shù)組。然后取數(shù)組的中間節(jié)點為根節(jié)點的值，左邊的都是小于它的值，右邊的都是大于它的值，再通過左右兩邊的數(shù)值去構造當前節(jié)點的左右子樹。最后當所有值都處理完，就構造完成了一顆高度平衡的二叉搜索樹。

代碼實現(xiàn)

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)
};

解題思路-優(yōu)化

上面的實現(xiàn)中我們每次都要切割 list 數(shù)組，其實可以更換為記錄左右下標的方式，即省去了切割數(shù)組的過程，又不用每次創(chuàng)建子數(shù)組。

代碼實現(xiàn)

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)
};

解題思路-進階

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

這里我們轉換思路，不去首先構造根節(jié)點，而是采用中序遍歷的順序構造目標二叉樹，這樣構造的順序就可以和遍歷鏈表的順序吻合，達到在遍歷鏈表的過程完成構造二叉樹。

代碼實現(xiàn)

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-有序鏈表轉換二叉搜索樹，更多關于前端算法有序鏈表轉換二叉搜索樹的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: