Cho mảng cây nhị phân tìm kiếm root và số nguyên k. Hãy tìm và trả về giá trị nhỏ thứ k (1-indexed) trong cây.
Ví dụ 1:
Input:
root = [3, 1, 4, null, 2]
k = 1
Output: 1Ví dụ 2:
Input:
root = [5, 3, 6, 2, 4, null, null, 1]
k = 3
Output: 3Định Dạng Đầu Vào (Input)
Dòng 1: Mảng root
Dòng 2: Số nguyên k
Dòng 2: Số nguyên k
Định Dạng Đầu Ra (Output)
Một số nguyên là phần tử nhỏ thứ k
Ràng Buộc (Constraints)
Số node trong cây từ 1 đến 10^41 <= k <= số node trong cây
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[3, 1, 4, null, 2]
1
Output:
1
Giải thích: Nhỏ nhất là 1
Ví dụ 2:
Input:
[5, 3, 6, 2, 4, null, null, 1]
3
Output:
3
Giải thích: Thứ tự tăng dần: [1, 2, 3, 4, 5, 6] -> số thứ 3 là 3
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.
Duyệt Trung Thứ Tự (In-order Traversal) O(n)
Duyệt In-order (Trái -> Gốc -> Phải) trên cây BST sinh ra dãy số tăng dần. Phần tử thứ k trong dãy chính là đáp án.
Dữ liệu đầu vào (Input):
[3, 1, 4, null, 2]
1
Kết quả kỳ vọng (Expected Output):
1
Dữ liệu đầu vào (Input):
[5, 3, 6, 2, 4, null, null, 1]
3
Kết quả kỳ vọng (Expected Output):
3
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
