前端算法leetcode109題解有序鏈表轉(zhuǎ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)文章!
相關(guān)文章
JavaScript與JQuery框架基礎(chǔ)入門教程
這篇文章主要介紹了jQuery和JavaScript入門基礎(chǔ)知識學(xué)習(xí)指南,jQuery是當(dāng)下最主流人氣最高的JavaScript庫,需要的朋友可以參考下2021-07-07微信小程序 彈框和模態(tài)框?qū)崿F(xiàn)代碼
這篇文章主要介紹了微信小程序 彈框和模態(tài)框?qū)崿F(xiàn)代碼的相關(guān)資料,需要的朋友可以參考下2017-03-03使用純JavaScript封裝一個(gè)消息提示條功能示例詳解
這篇文章主要為大家介紹了使用純JavaScript封裝一個(gè)消息提示條功能示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-02-02微信小程序之頁面跳轉(zhuǎn)和參數(shù)傳遞的實(shí)現(xiàn)
這篇文章主要介紹了微信小程序之頁面跳轉(zhuǎn)和參數(shù)傳遞的實(shí)現(xiàn)的相關(guān)資料,希望通過本文能幫助到大家,需要的朋友可以參考下2017-09-09