เราได้รับ Inorder และ Preorder traversal ของ Binary Tree เป้าหมายคือสร้างต้นไม้กลับจาก traversal ทั้งสอง
Inorder traversal − เยี่ยม left subtree ก่อน ตามด้วยโหนด แล้ว right subtree
Preorder traversal − เยี่ยมโหนดก่อน ตามด้วย left subtree แล้ว right subtree
Inorder และ Preorder ของต้นไม้ตัวอย่าง:
Inorder
2-3-4-5-6-8-10
Preorder
4-3-2-5-8-6-10
ตอนนี้เราจะสร้างต้นไม้กลับจาก Preorder และ Inorder ที่กำหนด:
Inorder
2-3-4-5-6-8-10
Preorder
5-3-2-4-8-6-10
- Preorder เยี่ยม root ก่อน ดังนั้นค่าแรก (5) คือ root ของต้นไม้
- จาก Inorder: ค่าด้านซ้ายของ 5 (2-3-4) เป็น left subtree, ด้านขวา (6-8-10) เป็น right subtree
- ทำซ้ำสำหรับ left subtree: Preorder = 3-2-4 → root = 3, Inorder = 2 ← 3 → 4
- ทำซ้ำสำหรับ right subtree: Preorder = 8-6-10 → root = 8, Inorder = 6 ← 8 → 10
ดังนั้นเราสร้างต้นไม้เดิมกลับมาได้จาก Preorder และ Inorder traversal
