資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目描述輸入一棵二叉搜索樹(shù)，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。
題目描述
輸入一棵二叉搜索樹(shù)，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。
分析如果是這樣一棵二叉搜索樹(shù)：
那么它對(duì)應(yīng)的雙向鏈表順序?yàn)椋?/p>
1 3 4 5 7 10 11 15
仔細(xì)觀察發(fā)現(xiàn)這個(gè)序列和樹(shù)的中序遍歷是一樣的，所以算法就好寫(xiě)了，先中序遍歷得到一個(gè)序列，然后再按照雙向鏈表的指針規(guī)則鏈接起來(lái)即可。
代碼實(shí)現(xiàn)/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Convert(r)
{
if(r === null)
return r;
var q = [], s = [];
var cur = r;
while(cur !== null || s.length !== 0) {
if(cur !== null){
s.push(cur);
cur = cur.left;
}else{
cur = s.pop();
q.push(cur);
cur = cur.right;
}
}
r = q.shift();
r.left = null;
r.right = null;
var tail = r;
cur = null;
while(q.length !== 0){
cur = q.shift();
tail.right = cur;
cur.left = tail;
tail = cur;
}
return r;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/95974.html
摘要：像剛才的這幅圖，就是二叉搜索樹(shù)。而我們本文要學(xué)習(xí)的內(nèi)容，就是如何寫(xiě)一個(gè)二叉搜索樹(shù)。但在二叉搜索樹(shù)中，我們把節(jié)點(diǎn)成為鍵，這是術(shù)語(yǔ)。前端路漫漫，且行且歌的前端樂(lè)園原文鏈接寒假前端學(xué)習(xí)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法四二叉搜索樹(shù) 本系列的第一篇文章: 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（一），棧與隊(duì)列第二篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（二）：鏈表第三篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)...
摘要：是棧，它繼承于。滿(mǎn)二叉樹(shù)除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹(shù)。沒(méi)有鍵值相等的節(jié)點(diǎn)。這是數(shù)據(jù)庫(kù)選用樹(shù)的最主要原因。 在我們學(xué)習(xí)Java的時(shí)候，很多人會(huì)面臨我不知道繼續(xù)學(xué)什么或者面試會(huì)問(wèn)什么的尷尬情況（我本人之前就很迷茫）。所以，我決定通過(guò)這個(gè)開(kāi)源平臺(tái)來(lái)幫助一些有需要的人，通過(guò)下面的內(nèi)容，你會(huì)掌握系統(tǒng)的Java學(xué)習(xí)以及面試的相關(guān)知識(shí)。本來(lái)是想通過(guò)Gitbook的...
摘要：有效二叉搜索樹(shù)定義如下節(jié)點(diǎn)的左子樹(shù)只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹(shù)和右子樹(shù)自身必須也是二叉搜索樹(shù)。而我們二叉搜索樹(shù)保證了左子樹(shù)的節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值均小于右子樹(shù)的值，因此中序遍歷以后得到的序列一定是升序序列。 ...
閱讀 3482·2021-09-02 09:53
閱讀 1804·2021-08-26 14:13
閱讀 2766·2019-08-30 15:44
閱讀 1324·2019-08-30 14:03
閱讀 1974·2019-08-26 13:42
閱讀 3025·2019-08-26 12:21
閱讀 1315·2019-08-26 11:54
閱讀 1909·2019-08-26 10:46
