您好,登錄后才能下訂單哦!
今天就跟大家聊聊有關(guān)怎么解析python二叉樹的中序遍歷,可能很多人都不太了解,為了讓大家更加了解,小編給大家總結(jié)了以下內(nèi)容,希望大家根據(jù)這篇文章可以有所收獲。
二叉樹的中序遍歷
給定一個(gè)二叉樹,返回它的 中序 遍歷。
示例:
輸入: [1,null,2,3]
輸出: [1,3,2]
進(jìn)階: 遞歸算法很簡(jiǎn)單,你可以通過迭代算法完成嗎?
用棧(Stack)的思路來處理問題。
中序遍歷的順序?yàn)?strong>左-根-右,具體算法為:
從根節(jié)點(diǎn)開始,先將根節(jié)點(diǎn)壓入棧
然后再將其所有左子結(jié)點(diǎn)壓入棧,取出棧頂節(jié)點(diǎn),保存節(jié)點(diǎn)值
再將當(dāng)前指針移到其右子節(jié)點(diǎn)上,若存在右子節(jié)點(diǎn),則在下次循環(huán)時(shí)又可將其所有左子結(jié)點(diǎn)壓入棧中
動(dòng)畫演示GIF加載有點(diǎn)慢,請(qǐng)稍待片刻加載顯示^_^
下面這種寫法使用了一個(gè)輔助結(jié)點(diǎn)p,這種寫法其實(shí)可以看作是一個(gè)模版,對(duì)應(yīng)的還有前序和后序的模版寫法,形式很統(tǒng)一,方便于記憶。上篇更新前序的和后面要更新后序文章中都會(huì)補(bǔ)充該寫法。思路與代碼如下:
輔助結(jié)點(diǎn)p初始化為根結(jié)點(diǎn),while循環(huán)的條件是棧不為空或者輔助結(jié)點(diǎn)p不為空
在循環(huán)中首先判斷如果輔助結(jié)點(diǎn)p存在,那么先將p加入棧中,此時(shí)p指向其左子結(jié)點(diǎn)
否則如果p不存在的話,表明沒有左子結(jié)點(diǎn),我們?nèi)〕鰲m斀Y(jié)點(diǎn),然后將p的結(jié)點(diǎn)值加入結(jié)果res中,將p指向棧頂結(jié)點(diǎn)的右子結(jié)點(diǎn)
看完上述內(nèi)容,你們對(duì)怎么解析python二叉樹的中序遍歷有進(jìn)一步的了解嗎?如果還想了解更多知識(shí)或者相關(guān)內(nèi)容,請(qǐng)關(guān)注億速云行業(yè)資訊頻道,感謝大家的支持。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。