Chuyển mảng phẳng thành cây lồng nhau (Flat Array to Nested Tree) | Đấu Trường Thuật Toán

Trong phát triển Web và API (như quản lý danh mục đa cấp, menu điều hướng đa tầng, sơ đồ tổ chức phòng ban), dữ liệu thường được lưu trữ trong CSDL dưới dạng bảng phẳng với trường parent_id.

Cho một mảng các đối tượng items, mỗi đối tượng có id, parent_id (0 là node gốc root) và name.

Hãy viết hàm chuyển đổi mảng phẳng này thành cấu trúc cây phân cấp lồng nhau, trong đó mỗi node có thêm thuộc tính children chứa danh sách các node con trực tiếp của nó.

Yêu cầu bắt buộc: Thuật toán phải đạt độ phức tạp thời gian O(n) (không sử dụng đệ quy lặp nhiều lần quét mảng O(n^2)).

Ví dụ 1:

Input:
[
  {"id": 1, "parent_id": 0, "name": "Lap trinh"},
  {"id": 2, "parent_id": 1, "name": "Frontend"},
  {"id": 3, "parent_id": 1, "name": "Backend"},
  {"id": 4, "parent_id": 0, "name": "Design"}
]
Output:
[
  {
    "id": 1,
    "parent_id": 0,
    "name": "Lap trinh",
    "children": [
      {"id": 2, "parent_id": 1, "name": "Frontend", "children": []},
      {"id": 3, "parent_id": 1, "name": "Backend", "children": []}
    ]
  },
  {
    "id": 4,
    "parent_id": 0,
    "name": "Design",
    "children": []
  }
]

Định Dạng Đầu Vào (Input)

Một dòng chứa mảng JSON items

Định Dạng Đầu Ra (Output)

Mảng JSON đại diện cho cây thư mục đã lồng nhau

Ràng Buộc (Constraints)

1 <= items.length <= 10^4
id và parent_id là các số nguyên không âm.

Ví Dụ Kiểm Thử Mẫu

Ví dụ 1:

Input:

[{"id":1,"parent_id":0,"name":"Lap trinh"},{"id":2,"parent_id":1,"name":"Frontend"},{"id":3,"parent_id":1,"name":"Backend"},{"id":4,"parent_id":0,"name":"Design"}]

Output:

[{"id":1,"parent_id":0,"name":"Lap trinh","children":[{"id":2,"parent_id":1,"name":"Frontend","children":[]},{"id":3,"parent_id":1,"name":"Backend","children":[]}]},{"id":4,"parent_id":0,"name":"Design","children":[]}]

Giải thích: Cây danh mục 2 cấp

Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.

Kỹ thuật Tham Chiếu Hash Map Một Lần Quét O(n)

1. Tạo một Hash Map lưu tham chiếu của mọi item theo id, khởi tạo thuộc tính children = [].
2. Quét qua mảng items một lần duy nhất:
- Nếu parent_id == 0: Đẩy item vào mảng kết quả roots.
- Nếu parent_id > 0: Tìm node cha trong Hash Map và đẩy item vào parent.children qua tham chiếu con trỏ.

Vui lòng đăng nhập

Đăng nhập tài khoản học viên để xem lịch sử nộp bài của bạn.

Đăng nhập