สร้าง Binary Tree จาก Preorder และ Postorder Traversal ใน Python

โจทย์: กำหนดลำดับ Preorder และ Postorder traversal สร้าง Binary Tree กลับคืนมา

ตัวอย่าง

Preorder: [1,2,4,5,3,6,7]
Postorder: [4,5,2,6,7,3,1]

ข้อสังเกต

• Preorder: Root → Left → Right
• Postorder: Left → Right → Root
• Root แรกของ Preorder = Root สุดท้ายของ Postorder
• Left subtree สิ้นสุดที่ค่าที่ตรงกับ Postorder[current]

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

1. สร้าง root จาก pre[0], push ลง stack
2. วนลูป pre[1..] และ post[0..]
3. ถ้า stack top == post[j] → pop, j++ (left subtree เสร็จ)
4. มิฉะนั้น สร้าง node ใหม่ ผูกเป็น left/right ของ stack top, push

ตัวอย่างโค้ด Python

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

class Solution(object):
    def constructFromPrePost(self, pre, post):
        if not pre:
            return None
        
        root = TreeNode(pre[0])
        stack = [root]
        i, j = 1, 0
        
        while i < len(pre) and j < len(post):
            # Left subtree เสร็จแล้ว
            if stack[-1].data == post[j]:
                stack.pop()
                j += 1
                continue
            
            # สร้าง node ใหม่
            node = TreeNode(pre[i])
            
            # ผูกเป็น left หรือ right
            if not stack[-1].left:
                stack[-1].left = node
            else:
                stack[-1].right = node
            
            stack.append(node)
            i += 1
        
        return root

# ฟังก์ชันช่วยพิมพ์ Level Order
def level_order(root):
    if not root:
        return []
    result, queue = [], [root]
    while queue:
        node = queue.pop(0)
        result.append(node.data)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return result

# ทดสอบ
ob = Solution()
pre = [1,2,4,5,3,6,7]
post = [4,5,2,6,7,3,1]
tree = ob.constructFromPrePost(pre, post)
print(level_order(tree))  # Output: [1, 2, 3, 4, 5, 6, 7]

ตัวอย่าง Input/Output

Input: [1,2,4,5,3,6,7] [4,5,2,6,7,3,1]
Output: [1, 2, 3, 4, 5, 6, 7] (Level Order)

ความซับซ้อน: Time O(n), Space O(n)