Python程式設計中的二叉樹後序遍歷

C++伺服器端程式設計程式設計

假設我們有一個二叉樹。我們必須使用迭代方法找到這棵樹的後序遍歷。如果樹是這樣的：

那麼輸出將是：[9,15,7,10,-10]

為了解決這個問題，我們將遵循以下步驟：

如果根節點為空，則返回空陣列
建立一個數組ret
stack := 定義一個包含[root, 0]對的棧
當棧不為空時：
- node := 棧頂元素，然後從棧中刪除該元素。
- 如果節點對的第二個值是0，則
  - current := 節點對的第一個值
  - 將一個(current, 1)對插入到棧中
  - 如果current的右子節點存在
    - 將一個[current的右子節點, 0]對插入到棧中
  - 如果current的左子節點存在：
    - 將一個[current的左子節點, 0]對插入到棧中
- 否則，當節點對第一個值的第二個值不為0時，將節點對第一個值的資料插入到res中
返回res

讓我們看看下面的實現來更好地理解：

示例

線上演示

class TreeNode:
def __init__(self, data, left = None, right = None):
   self.data = data
   self.left = left
   self.right = right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution(object):
   def postorderTraversal(self, root):
      if not root:
         return []
      res = []
      stack = [[root,0]]
      while stack:
         node = stack[-1]
         stack.pop()
         if node[1]== 0 :
            current = node[0]
            stack.append([current,1])
            if current.right:
               stack.append([current.right,0])
            if current.left:
               stack.append([current.left,0])
         else:
            if node[0].data != 0:
               res.append(node[0].data)
      return res
ob = Solution()
root = make_tree([-10,9,10,None,None,15,7])
print(ob.postorderTraversal(root))

輸入

[-10,9,10,None,None,15,7]

輸出

[9, 15, 7, 10, -10]

Arnab Chakraborty

更新於：2020年6月9日

179 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習