溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

怎么解析python二叉樹的后序遍歷

發(fā)布時(shí)間：2021-12-13 16:00:37 來源：億速云 閱讀：142 作者：柒染 欄目：大數(shù)據(jù)

怎么解析python二叉樹的后序遍歷，針對(duì)這個(gè)問題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問題的小伙伴找到更簡單易行的方法。

二叉樹的后序遍歷

題目

給定一個(gè)二叉樹，返回它的 后序 遍歷。

 
示例:

輸入: [1,null,2,3]

輸出: [3,2,1]

進(jìn)階: 遞歸算法很簡單，你可以通過迭代算法完成嗎？

解題思路

用棧(Stack)的思路來處理問題。

后序遍歷的順序?yàn)?strong>左-右-根，具體算法為：

  • 先將根結(jié)點(diǎn)壓入棧，然后定義一個(gè)輔助結(jié)點(diǎn)head

  • while循環(huán)的條件是棧不為空

  • 在循環(huán)中，首先將棧頂結(jié)點(diǎn)t取出來

  • 如果棧頂結(jié)點(diǎn)沒有左右子結(jié)點(diǎn)，或者其左子結(jié)點(diǎn)是head，或者其右子結(jié)點(diǎn)是head的情況下。我們將棧頂結(jié)點(diǎn)值加入結(jié)果res中，并將棧頂元素移出棧，然后將head指向棧頂元素

  • 否則的話就看如果右子結(jié)點(diǎn)不為空，將其加入棧

  • 再看左子結(jié)點(diǎn)不為空的話，就加入棧

動(dòng)畫演示

動(dòng)畫演示GIF加載有點(diǎn)慢，請(qǐng)稍等片刻加載顯示^_^

怎么解析python二叉樹的后序遍歷

參考代碼

怎么解析python二叉樹的后序遍歷

補(bǔ)充

下面這種寫法使用了一個(gè)輔助結(jié)點(diǎn)p，這種寫法其實(shí)可以看作是一個(gè)模版，對(duì)應(yīng)的還有前序和后序的模版寫法，形式很統(tǒng)一，方便于記憶。上上篇更新前序的和上篇更新的中序文章中都會(huì)補(bǔ)充該寫法。思路與代碼如下：

  • 先將先序遍歷的根-左-右順序變?yōu)楦?右-左

  • 再翻轉(zhuǎn)變?yōu)楹笮虮闅v的左-右-根，翻轉(zhuǎn)還是改變結(jié)果res的加入順序

  • 然后把更新輔助結(jié)點(diǎn)p的左右順序換一下即可

怎么解析python二叉樹的后序遍歷

關(guān)于怎么解析python二叉樹的后序遍歷問題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識(shí)。

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手