Giả sử ta có một cây nhị phân, ta phải tìm nhìn từ trên (top view) của cây, các nút được sắp xếp từ trái sang phải.
Ví dụ: đầu vào như hình, đầu ra = [3, 5, 8, 6, 9], vì 3 che 2 và 5 che 7 nên không thấy.
Để giải quyết, ta làm theo các bước:
- view := map rỗng.
- q := hàng đợi hai đầu.
- Thêm cặp (root, 0) vào q.
- start := inf, end := -inf.
- while q không rỗng:
- (node, coord) := lấy phần tử trái q.
- start := min(start, coord), end := max(end, coord).
- Nếu coord chưa có trong view: view[coord] = giá trị node.
- Nếu node.left không null: thêm (node.left, coord-1) vào q.
- Nếu node.right không null: thêm (node.right, coord+1) vào q.
- res := danh sách rỗng.
- for i từ start đến end: nếu i trong view: thêm view[i] vào res.
- Trả về res.
Xem triển khai dưới đây:
Ví dụ
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 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))
Đầu vào
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)
Đầu ra
[3, 5, 8, 6, 9]