Cho thứ tự trước (preorder) của một cây tìm kiếm nhị phân (BST). Kiểm tra xem mỗi nút nội bộ có đúng một con hay không.
Ví dụ: preorder = [22, 12, 13, 15, 14] → True.
Giải thuật hiệu quả
- Với BST, tất cả con cháu của một nút đều hoặc lớn hơn hoặc nhỏ hơn nút đó.
- Tính hiệu giữa nút hiện tại và nút tiếp theo (
next = preorder[i] - preorder[i+1]). - Tính hiệu giữa nút hiện tại và nút cuối cùng (
last = preorder[i] - preorder[-1]). - Nếu
next * last < 0(dấu khác nhau) → nút đó có hai con → trả vềFalse.
Mã ví dụ
def solve(preorder):
next_diff = 0
last_diff = 0
for i in range(len(preorder)-1):
next_diff = preorder[i] - preorder[i+1]
last_diff = preorder[i] - preorder[-1]
if next_diff * last_diff < 0:
return False
return True
preorder = [22, 12, 13, 15, 14]
print(solve(preorder))
Đầu vào
[22, 12, 13, 15, 14]
Đầu ra
True