Cho mảng root biểu diễn cây nhị phân. Hãy xác định xem cây này có phải là Cây nhị phân tìm kiếm hợp lệ (BST) hay không.
Một BST hợp lệ thỏa mãn:
- Mọi node thuộc cây con bên trái đều có giá trị nhỏ hơn node hiện tại.
- Mọi node thuộc cây con bên phải đều có giá trị lớn hơn node hiện tại.
- Cả cây con trái và phải đều phải là BST hợp lệ.
Ví dụ 1:
Input: root = [2, 1, 3]
Output: trueVí dụ 2:
Input: root = [5, 1, 4, null, null, 3, 6]
Output: false
Giải thích: Node gốc là 5 nhưng con phải là 4 (< 5).Định Dạng Đầu Vào (Input)
Một dòng chứa mảng root
Định Dạng Đầu Ra (Output)
true hoặc false
Ràng Buộc (Constraints)
Số node trong cây [1, 10^4]-2^31 <= Node.val <= 2^31 - 1
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[2, 1, 3]
Output:
true
Giải thích: BST hợp lệ
Ví dụ 2:
Input:
[5, 1, 4, null, null, 3, 6]
Output:
false
Giải thích: 4 nhỏ hơn 5 ở cây con phải
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 Giới Hạn Khoảng Giá Trị (Min, Max) O(n)
Khi đi xuống con trái, cập nhật max = node.val. Khi đi xuống con phải, cập nhật min = node.val.
Dữ liệu đầu vào (Input):
[2, 1, 3]
Kết quả kỳ vọng (Expected Output):
true
Dữ liệu đầu vào (Input):
[5, 1, 4, null, null, 3, 6]
Kết quả kỳ vọng (Expected Output):
false
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...
