快捷導(dǎo)航

解決Python3中二叉樹前序遍歷的迭代問題

更新時(shí)間：2022年09月06日 08:36:23 作者：amboke

二叉樹是分層數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)父節(jié)點(diǎn)最多有 2 個(gè)子節(jié)點(diǎn)，在今天的文章中，我們將討論一個(gè)在大量技術(shù)編碼面試中出現(xiàn)的重要主題，對(duì)Python二叉樹遍歷相關(guān)知識(shí)感興趣的朋友一起看看吧

Python3中二叉樹前序遍歷的迭代解決方案

A Binary Tree

二叉樹是分層數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)父節(jié)點(diǎn)最多有 2 個(gè)子節(jié)點(diǎn)。在今天的文章中，我們將討論一個(gè)在大量技術(shù)編碼面試中出現(xiàn)的重要主題。

問題陳述：鑒于 根 二叉樹，返回其節(jié)點(diǎn)值的前序遍歷 . 提供迭代解決方案而不是遞歸解決方案。

解決方案：

預(yù)購(gòu)遍歷在二叉樹中按以下順序發(fā)生：

先訪問根
遍歷左子樹
遍歷右子樹

為了用迭代解決方案解決這個(gè)問題，我們必須實(shí)現(xiàn) 堆數(shù)據(jù)結(jié)構(gòu)。這是一種非線性數(shù)據(jù)結(jié)構(gòu)，其中操作按 LIFO（后進(jìn)先出）順序執(zhí)行。我們回答的方法很簡(jiǎn)單，如下所示：

我們將初始化兩個(gè)列表 IE 一個(gè)承載輸出，另一個(gè)充當(dāng)我們的堆棧數(shù)據(jù)結(jié)構(gòu)。堆棧將使用二叉樹的根值進(jìn)行初始化。
然后，只要堆棧有值，我們就會(huì)在堆棧上執(zhí)行一個(gè) while 循環(huán)。在循環(huán)中，依次進(jìn)行以下操作：
刪除（彈出）堆棧中最頂部的值（根節(jié)點(diǎn)）并將其附加到輸出列表
將彈出值的右孩子壓入堆棧
將彈出值的左孩子壓入堆棧
返回循環(huán)結(jié)束時(shí)的輸出列表

作為這個(gè)過程的結(jié)果，將首先訪問根值，然后訪問左子樹，最后訪問右子樹值。

需要注意的是，右孩子首先被推入堆棧，然后是左孩子。這是因?yàn)槎褩５?LIFO 特性。這樣做將允許我們先訪問左孩子，然后再訪問右孩子。

說話很便宜，給我看代碼：

 # 二叉樹節(jié)點(diǎn)的定義 類樹節(jié)點(diǎn)：  
 def __init__(self, val=0, left=None, right=None):  
 自我.val = val  
 self.left = 左  
 self.right = 對(duì) 類解決方案：  
 def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:  
 輸出，節(jié)點(diǎn)堆棧 = []，[根]  
          
 而節(jié)點(diǎn)堆棧：  
 節(jié)點(diǎn) = nodestack.pop()  
 if node: # preorder: root -> left -> right  
 output.append(node.val)  
 nodestack.append(node.right)  
 nodestack.append(node.left)  
 返回輸出

如果這篇文章對(duì)您有幫助，請(qǐng)隨意喜歡并訂閱我的時(shí)事通訊，以獲取更多 Python 中的 DSA 內(nèi)容。

到此這篇關(guān)于Python3中二叉樹前序遍歷的迭代解決方案的文章就介紹到這了,更多相關(guān)Python二叉樹遍歷內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: