前端算法題解leetcode114二叉樹展開為鏈表
正文
給你二叉樹的根結(jié)點(diǎn) root
,請(qǐng)你將它展開為一個(gè)單鏈表:
- 展開后的單鏈表應(yīng)該同樣使用
TreeNode
,其中right
子指針指向鏈表中下一個(gè)結(jié)點(diǎn),而左子指針始終為null
。 - 展開后的單鏈表應(yīng)該與二叉樹 先序遍歷 順序相同。
示例 1:
輸入: root = [1,2,5,3,4,null,6]
輸出: [1,null,2,null,3,null,4,null,5,null,6]
示例 2:
輸入: root = []
輸出: []
示例 3:
輸入: root = [0]
輸出: [0
提示:
- 樹中結(jié)點(diǎn)數(shù)在范圍
[0, 2000]
內(nèi) -100 <= Node.val <= 100
進(jìn)階: 你可以使用原地算法(O(1)
額外空間)展開這棵樹嗎?
解題思路-基礎(chǔ)
本題要求我們把二叉樹拆成單鏈表,但是其實(shí)仍然是二叉樹,只不過每個(gè)子樹只有右子樹。
最簡(jiǎn)單的辦法就是前序遍歷二叉樹,將節(jié)點(diǎn)放入數(shù)組,然后遍歷前序遍歷獲取到的節(jié)點(diǎn)數(shù)組,構(gòu)造結(jié)果二叉樹。
代碼實(shí)現(xiàn)
function treeToList(root){ const list = [] function preorder(node){ if(node === null){ return } list.push(node) preorder(node.left) preorder(node.right) } preorder(root) return list } var flatten = function(root) { if(root === null){ return null } const list = treeToList(root) for(let i = 1;i<list.length;i++){ list[i-1].left = null list[i-1].right = list[i] } }
解題思路-進(jìn)階
上面的解題思路可以完成解題,但是沒有達(dá)到本題進(jìn)階的要求:使用原地算法(O(1)
額外空間)展開這棵樹。
想要達(dá)到進(jìn)階的要求,就只能使用常量的額外空間,這里其實(shí)我們可以借用一個(gè) current
變量指向當(dāng)前正在處理的節(jié)點(diǎn),同樣是前序遍歷,每次把當(dāng)前節(jié)點(diǎn)掛到 current
的右子樹上,同時(shí)把 current
的左子樹置為 null
,防止出現(xiàn)循環(huán)引用,然后繼續(xù)處理后續(xù)節(jié)點(diǎn),這樣當(dāng)前序遍歷完成,就把二叉樹處理成了單鏈表狀態(tài)。
代碼實(shí)現(xiàn)
var flatten = function(root) { if(root === null){ return null } let current = {} function preorder(node){ if(node === null){ return } current.left = null current.right = node current = current.right const left = current.left const right = node.right preorder(left) preorder(right) } preorder(root) }
至此我們就完成了 leetcode-114-二叉樹展開為鏈表,更多關(guān)于前端算法二叉樹展開為鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
原生JavaScript實(shí)現(xiàn)批量獲取表單數(shù)據(jù)
這篇文章主要為大家詳細(xì)介紹了如何使用原生JavaScript實(shí)現(xiàn)批量獲取表單數(shù)據(jù),文中的示例代碼講解詳細(xì),有需要的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-01-01JS中‘hello’與new String(‘hello’)引出的問題詳解
這篇文章主要給大家介紹了關(guān)于JS中'hello'與new String('hello')引出的問題的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考借鑒,下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2018-08-08axios使用攔截器統(tǒng)一處理所有的http請(qǐng)求的方法
這篇文章主要介紹了axios使用攔截器統(tǒng)一處理所有的http請(qǐng)求的方法,通過一段實(shí)例代碼給大家介紹了axios攔截器使用,代碼簡(jiǎn)單易懂,非常不錯(cuò),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2018-11-11JS實(shí)現(xiàn)自動(dòng)閱讀單詞(有道單詞本添加功能)
有道單詞客戶Duan沒有自動(dòng)閱讀的功能, 本文用強(qiáng)大的js實(shí)現(xiàn)了簡(jiǎn)單的自動(dòng)下一個(gè)單詞的功能,需要的朋友可以參考下2016-11-11探索JavaScript函數(shù)的無限可能(函數(shù)基本概念)
JavaScript中的函數(shù)是一種重要的編程概念,它允許我們封裝可重用的代碼塊,并在需要時(shí)進(jìn)行調(diào)用,本文將深入介紹JavaScript函數(shù)的各個(gè)方面,包括函數(shù)定義和調(diào)用、參數(shù)和返回值、作用域和閉包、高階函數(shù)以及常見的函數(shù)應(yīng)用場(chǎng)景,感興趣的朋友一起看看吧2023-08-08用js判斷頁面刷新或關(guān)閉的方法(onbeforeunload與onunload事件)
Onunload,onbeforeunload都是在刷新或關(guān)閉時(shí)調(diào)用,可以在<script>腳本中通過window.onunload來指定或者在<body>里指定2012-06-06