Mô tả
Tại Trung Tâm Bưu Chính, mỗi ngày có hàng nghìn bưu phẩm đổ về. Để thao tác kiểm tra nhanh, nhân viên kho quyết định lưu mã định danh của từng bưu phẩm lên một cây tìm kiếm nhị phân (BST). Quy tắc rất đơn giản: mọi mã bên trái nút gốc luôn nhỏ hơn mã gốc, và mọi mã bên phải luôn lớn hơn mã gốc.
Hôm nay bạn phụ trách ca trực. Nhiệm vụ của bạn là nhận một danh sách mã bưu phẩm, chèn lần lượt vào cây rỗng (theo đúng thứ tự xuất hiện trong danh sách), rồi thực hiện duyệt giữa (trái – gốc – phải) để xuất ra danh sách mã theo chiều tăng dần phục vụ biên bản kiểm kê.
Đầu vào
- Dòng đầu chứa số nguyên
n— số lượng bưu phẩm. - Dòng thứ hai chứa
nsố nguyêna[0], a[1], ..., a[n-1]— các mã bưu phẩm, chèn theo đúng thứ tự từ trái qua phải.
Đầu ra
- Một dòng chứa
nsố nguyên là kết quả duyệt giữa cây BST, in ra từ nhỏ đến lớn, cách nhau bởi một khoảng trắng.
Ràng buộc
1 ≤ n ≤ 10^5-10^9 ≤ a[i] ≤ 10^9- Các mã có thể trùng nhau. Khi gặp mã trùng, vẫn tạo một nút mới và chèn về bên phải theo quy tắc dấu lớn hơn hoặc bằng.
Ví dụ
Ví dụ 1
Đầu vào:
7 50 30 70 20 40 60 80
Quá trình chèn tạo ra cây gốc 50, nhánh trái 30 (có con 20, 40), nhánh phải 70 (có con 60, 80). Duyệt giữa thu được danh sách tăng dần.
Đầu ra:
20 30 40 50 60 70 80
Ví dụ 2
Đầu vào:
5 10 10 10
Mỗi lần gặp mã trùng 10, ta vẫn tạo nút mới và rẽ phải, tạo thành nhánh lệch phải. Duyệt giữa vẫn xuất ra ba số 10 theo thứ tự chèn.
Đầu ra:
10 10 10