Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

Binary Tree Postorder Traversal ใน Python


สมมติว่าเรามีต้นไม้ไบนารี เราต้องหาการข้ามผ่านคำสั่งหลังของทรีนี้โดยใช้วิธีการวนซ้ำ ดังนั้นถ้าต้นไม้เป็นเหมือน −

Binary Tree Postorder Traversal ใน Python

จากนั้นผลลัพธ์จะเป็น:[9,15,7,10,-10]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • หากรูทเป็นค่าว่าง ให้คืนค่าอาร์เรย์ว่าง

  • สร้างอาร์เรย์ ret

  • stack :=กำหนด stack ด้วยคู่ [root, 0]

  • ในขณะที่สแต็กไม่ว่างเปล่า -

    • node :=ด้านบนของ stack จากนั้นลบองค์ประกอบออกจาก stack

    • หากค่าที่สองของคู่โหนดเป็น 0 แล้ว

      • ปัจจุบัน :=ค่าแรกของคู่โหนด

      • ใส่คู่ (ปัจจุบัน 1) ลงในกอง

      • หากมีกระแสไฟ -

        • แทรกคู่ [ขวาของกระแส 0] ลงในสแต็ก

      • หากมีกระแสเหลืออยู่ -

        • แทรกคู่ [ซ้ายของกระแส 0] ลงในสแต็ก

    • มิฉะนั้นเมื่อข้อมูลของโหนดคู่ค่าแรกไม่ใช่ 0 แล้วจึงแทรกข้อมูลของค่าแรกของโหนดลงใน 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]