ภาพรวม
โจทย์สร้าง Binary Tree จาก inorder และ postorder traversal sequences
หลักการ
- Postorder: Left, Right, Root → ตัวสุดท้ายคือ Root
- Inorder: Left, Root, Right → หา Root ใน inorder แบ่ง Left/Right subtree
- Recursive build
ตัวอย่าง
Inorder: [9, 3, 15, 20, 7]
Postorder: [9, 15, 7, 20, 3]
Root = 3 (postorder[-1])
Inorder: Left=[9], Root=3, Right=[15,20,7]
Recursive build subtrees
โค้ด Python
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def print_tree(root):
if root:
print_tree(root.left)
print(root.data, end=', ')
print_tree(root.right)
class Solution:
def buildTree(self, inorder, postorder):
if inorder:
root = TreeNode(postorder.pop())
ind = inorder.index(root.data)
root.right = self.buildTree(inorder[ind+1:], postorder)
root.left = self.buildTree(inorder[:ind], postorder)
return root
ob1 = Solution()
print_tree(ob1.buildTree([9,3,15,20,7], [9,15,7,20,3]))
ข้อสังเกต
postorder.pop()แก้ไขลิสต์ต้นฉบับ (destructive)inorder.index()หา index ใช้เวลา O(n) รวม O(n²) worst case- เพิ่มประสิทธิภาพ: สร้าง dict {value: index} สำหรับ inorder
ผลลัพธ์
9, 3, 15, 20, 7,
