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

กำหนด inorder และ postorder traversal สร้าง binary tree กลับมา

หลักการ

• Postorder: Left, Right, Root → ตัวสุดท้ายคือ Root
• Inorder: Left, Root, Right → หา Root แล้วแบ่งซ้าย/ขวาได้

ตัวอย่าง

Inorder:   [9, 15, 7, 20, 3]
Postorder: [9, 3, 15, 20, 7]
Tree:        7
           /   \
          9     20
              /  \
             15   3

โค้ด

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

class Solution:
    def buildTree(self, inorder, postorder):
        if not inorder:
            return None
        
        root_val = postorder.pop()  # last = root
        root = TreeNode(root_val)
        idx = inorder.index(root_val)
        
        # สำคัญ: build right ก่อน เพราะ postorder.pop() ดึงจากท้าย
        root.right = self.buildTree(inorder[idx+1:], postorder)
        root.left = self.buildTree(inorder[:idx], postorder)
        return root

# Helper: print inorder
def print_inorder(root):
    if root:
        print_inorder(root.left)
        print(root.val, end=' ')
        print_inorder(root.right)

# ทดสоб
inorder = [9, 15, 7, 20, 3]
postorder = [9, 3, 15, 20, 7]
sol = Solution()
tree = sol.buildTree(inorder, postorder)
print_inorder(tree)  # 9 15 7 20 3

สรุป

Recursive: pop postorder หา root, index ใน inorder แบ่งซ้าย/ขวา สร้าง right ก่อน left