ภาพรวม
โจทย์สร้าง BST จาก postorder traversal โดยใช้ข้อเท็จจริงว่า Inorder ของ BST = sorted(postorder)
ตัวอย่าง
Postorder: [3, 9, 20, 15, 7]
Inorder (sorted): [3, 7, 9, 15, 20]
Tree ที่ได้ (Inorder print): 3, 7, 9, 15, 20
โค้ด 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()
postorder = [3, 9, 20, 15, 7]
inorder = sorted(postorder)
print_tree(ob1.buildTree(inorder, postorder))
ความแตกต่างจาก Binary Tree ทั่วไป
- Binary Tree: ต้องให้ inorder และ postorder ทั้งคู่
- BST: ให้ postorder เพียงอย่างเดียว เพราะ inorder = sorted(postorder) เสมอ
ผลลัพธ์
3, 7, 9, 15, 20,
