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

A Binary Tree

二叉樹是分層數據結構，其中每個父節點最多有 2 個子節點。在今天的文章中，我們將討論一個在大量技術編碼面試中出現的重要主題。

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

解決方案：

預購遍歷 在二叉樹中按以下順序發生：

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

為了用迭代解決方案解決這個問題，我們必須實現 堆 數據結構。這是一種非線性數據結構，其中操作按 LIFO（后進先出）順序執行。我們回答的方法很簡單，如下所示：

• 我們將初始化兩個列表?IE?一個承載輸出，另一個充當我們的堆棧數據結構。堆棧將使用二叉樹的根值進行初始化。
• 然后，只要堆棧有值，我們就會在堆棧上執行一個 while 循環。在循環中，依次進行以下操作：
• 刪除（彈出）堆棧中最頂部的值（根節點）并將其附加到輸出列表
• 將彈出值的右孩子壓入堆棧
• 將彈出值的左孩子壓入堆棧
• 返回循環結束時的輸出列表

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

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

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

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

如果這篇文章對您有幫助，請隨意喜歡并訂閱我的時事通訊，以獲取更多 Python 中的 DSA 內容。