สมมติว่าเรามีต้นไม้ไบนารี เราต้องหาการข้ามผ่านคำสั่งหลังของทรีนี้โดยใช้วิธีการวนซ้ำ ดังนั้นถ้าต้นไม้เป็นเหมือน −
จากนั้นผลลัพธ์จะเป็น:[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]
