การท่องต้นไม้แบบ Postorder แบบ Iterative ใน Python

บทนำ

Postorder Traversal (ท่องหลัง) คือการเยี่ยมชมโหนดในลำดับ Left → Right → Root โดยปกติมักใช้ Recursion แต่นี่คือวิธีทำแบบ Iterative (วนลูป) โดยใช้ Stack พร้อมสถานะ (State) เพื่อจำลองการทำงานของ Recursion

อัลกอริทึม (ขั้นตอน)

ถ้า Root เป็น null ให้คืนค่า Empty List
สร้าง Stack เก็บคู่ [node, state] โดย state = 0 = ยังไม่ประมวลผลลูก, 1 = ประมวลผลลูกแล้ว พร้อมเก็บค่า
Push [root, 0] เข้า Stack
วนลูปจน Stack ว่าง:
- Pop ข้อมูลบนสุด: node, state
- ถ้า state == 0:
  - Push [node, 1] กลับเข้าไป (マークว่าจะกลับมาก็บันทึกค่า)
  - Push [node.right, 0] ถ้ามี (Right ก่อนเพราะ Stack LIFO)
  - Push [node.left, 0] ถ้ามี
- ถ้า state == 1: เพิ่ม node.val เข้า Result
คืนค่า Result

การทำงานภาพรวม

Stack จำลอง Call Stack ของ Recursion โดย state=0 คือ "เข้าฟังก์ชันครั้งแรก" และ state=1 คือ "กลับมาจากลูกแล้ว พร้อมประมวลผลตัวเอง"

โค้ด Python

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def insert(temp, data):
    que = [temp]
    while que:
        temp = que.pop(0)
        if not temp.left:
            temp.left = TreeNode(data) if data is not None else TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            temp.right = TreeNode(data) if data is not None else TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    root = TreeNode(elements[0])
    for element in elements[1:]:
        insert(root, element)
    return root

class Solution:
    def postorderTraversal(self, root):
        if not root:
            return []
        res = []
        stack = [[root, 0]]
        while stack:
            node, state = stack.pop()
            if state == 0:
                stack.append([node, 1])
                if node.right:
                    stack.append([node.right, 0])
                if node.left:
                    stack.append([node.left, 0])
            else:
                if node.data != 0:  # ข้ามค่า placeholder 0
                    res.append(node.data)
        return res

# ทดสอบ
ob = Solution()
root = make_tree([-10, 9, 10, None, None, 15, 7])
print(ob.postorderTraversal(root))  # [9, 15, 7, 10, -10]

โครงสร้างต้นไม้ทดสอบ

Input

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

Output

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

ความซับซ้อน

Time: O(n) - เยี่ยมชมแต่ละโหนด 1 ครั้ง
Space: O(h) - h = ความสูงของต้นไม้ (Stack depth)