บทนำ
ในบทช่วยสอนนี้ เราจะหา Top View (มุมมองจากด้านบน) ของ Binary Tree โดยใช้ Python
Top View คืออะไร?
มองต้นไม้จากด้านบน โหนดที่มองเห็นคือโหนดที่มี horizontal distance (HD) แต่ละค่า ตัวแรกที่เจอ (ระดับตื้นที่สุด) HD: ราก=0, ซ้าย=-1, ขวา=+1, ซ้ายของซ้าย=-2, ฯลฯ
ตัวอย่าง
Input tree:
5
/ \
3 8
/ \
7 6
/ \
2 9
Output: [3, 5, 8, 6, 9]
(3 ซ้อน 2, 5 ซ้อน 7 → มองเห็นแค่ 3 และ 5)
อัลกอริทึม: BFS + Horizontal Distance
- ใช้ Queue เก็บคู่ (node, hd)
- Map/ดิกชันนารี view[hd] = ค่าโหนดแรกที่เจอที่ hd นั้น
- BFS: ดึง node, ถ้า hd ยังไม่มีใน view → ใส่เข้าไป
- เพิ่มลูกซ้าย (hd-1) และลูกขวา (hd+1) เข้า queue
- ติดตาม hd min/max เพื่อพิมพ์เรียงซ้าย-ขวา
ตัวอย่างโค้ด (Python)
from collections import deque
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
class Solution:
def solve(self, root):
view = {}
q = deque()
q.append((root, 0))
start = float("inf")
end = float("-inf")
while q:
node, coord = q.popleft()
start = min(start, coord)
end = max(end, coord)
if coord not in view:
view[coord] = node.val
if node.left:
q.append((node.left, coord - 1))
if node.right:
q.append((node.right, coord + 1))
res = []
for i in range(start, end + 1):
if i in view:
res.append(view[i])
return res
# Test
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.right.left = TreeNode(7)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(2)
root.right.right.right = TreeNode(9)
print(ob.solve(root)) # [3, 5, 8, 6, 9]
ผลลัพธ์
[3, 5, 8, 6, 9]
ความแตกต่างกับ Bottom View
Top View: เก็บโหนดแรกที่เจอแต่ละ HD (BFS ให้ระดับตื้นสุดก่อน)
Bottom View: เก็บโหนดสุดท้ายที่เจอแต่ละ HD (overwrite ทุกครั้ง)
สรุป
Top View ใช้ BFS + horizontal distance mapping O(n) เวลาและพื้นที่ หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ
