กำหนด preorder และ inorder traversal สร้าง binary tree กลับมา
หลักการ
- Preorder: Root, Left, Right → ตัวแรกคือ Root
- Inorder: Left, Root, Right → หา Root แล้วแบ่งซ้าย/ขวาได้
ตัวอย่าง
Preorder: [3, 9, 20, 15, 7]
Inorder: [9, 3, 15, 20, 7]
Tree: 3
/ \
9 20
/ \
15 7
โค้ด
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, preorder, inorder):
if not inorder:
return None
root_val = preorder.pop(0) # first = root
root = TreeNode(root_val)
idx = inorder.index(root_val)
root.left = self.buildTree(preorder, inorder[:idx])
root.right = self.buildTree(preorder, inorder[idx+1:])
return root
# ทดสอบ
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
sol = Solution()
tree = sol.buildTree(preorder, inorder)
def print_inorder(root):
if root:
print_inorder(root.left)
print(root.val, end=' ')
print_inorder(root.right)
print_inorder(tree) # 9 3 15 20 7
เพิ่มประสิทธิภาพด้วย HashMap (O(n))
class Solution:
def buildTree(self, preorder, inorder):
idx_map = {val: i for i, val in enumerate(inorder)}
self.pre_idx = 0
def helper(left, right):
if left > right:
return None
root_val = preorder[self.pre_idx]
self.pre_idx += 1
root = TreeNode(root_val)
idx = idx_map[root_val]
root.left = helper(left, idx - 1)
root.right = helper(idx + 1, right)
return root
return helper(0, len(inorder) - 1)
สรุป
Preorder pop(0) หรือใช้ index pointer + hashmap ให้ O(n) time
