Tuần tự hóa và Khôi phục Cây nhị phân (Serialize & Deserialize)

Mục tiêu kiến thức

• Hiểu bài toán Tuần tự hóa (Serialization): Chuyển đổi một cây nhị phân thành chuỗi ký tự phẳng để truyền qua mạng hoặc ghi xuống tệp.
• Khôi phục (Deserialization): Tái tạo chính xác cây ban đầu từ chuỗi ký tự.
• Sử dụng thuật toán duyệt theo mức (Level-order BFS) với ký hiệu nút rỗng đặc biệt null.

Mô tả bài toán

Cho chuỗi tuần tự hóa của một cây nhị phân theo thứ tự BFS (các nút ngăn cách bởi dấu phẩy, nút rỗng ký hiệu là null). Hãy khôi phục lại cây nhị phân và in ra tổng giá trị của tất cả các nút lá trong cây.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• Số nút trong cây N ≤ 10⁵.
• Giá trị mỗi nút -10⁹ ≤ V_i ≤ 10⁹.
• Thời gian: 1000ms. Bộ nhớ: 256MB.