前端算法leetcode109題解有序鏈表轉(zhuǎn)換二叉搜索樹

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

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

題目

題目地址

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

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

示例 1:

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

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

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

示例 2:

輸入: head = []

輸出: []

提示:

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

解題思路-基礎(chǔ)

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

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

代碼實(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(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)化

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

代碼實(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)
};

解題思路-進(jìn)階

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

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

代碼實(shí)現(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-有序鏈表轉(zhuǎn)換二叉搜索樹，更多關(guān)于前端算法有序鏈表轉(zhuǎn)換二叉搜索樹的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: