สร้าง BST จาก Postorder Traversal ด้วย Stack ใน Python

ภาพรวม

โจทย์สร้าง Binary Search Tree (BST) จาก postorder traversal sequence โดยใช้ Stack (Iterative approach)

ตัวอย่าง

Postorder: [6, 12, 10, 55, 45, 15]

BST ที่ได้ (Inorder): 6 10 12 15 45 55

อัลกอริทึม Stack-based

1. ราก = ตัวสุดท้ายของ postorder (15)
2. Push root ลง stack
3. เดิน postorder จากท้ายไปหน้า (i = n-2 downto 0):
   • สร้างโหนดใหม่ x = postorder[i]
   • Pop stack จนกว่า top < x (เจอ parent ที่ x เป็น right child)
   • ถ้า pop ไปแล้วมี temp → x เป็น left child ของ temp
   • ถ้าไม่ pop → x เป็น right child ของ stack top
   • Push x ลง stack

โค้ด Python

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

def solve(postorder):
    n = len(postorder)
    root = TreeNode(postorder[n - 1])
    stk = [root]
    i = n - 2
    while i >= 0:
        x = TreeNode(postorder[i])
        temp = None
        while stk and postorder[i] < stk[-1].val:
            temp = stk.pop()
        if temp:
            temp.left = x
        else:
            stk[-1].right = x
        stk.append(x)
        i -= 1
    return root

def inord(node):
    if node:
        inord(node.left)
        print(node.val, end=" ")
        inord(node.right)

postorder = [6, 12, 10, 55, 45, 15]
root = solve(postorder)
print("Inorder traversal:", end=" ")
inord(root)

ผลลัพธ์

6 10 12 15 45 55