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