Giả sử chúng ta có trình duyệt đặt hàng trước của cây tìm kiếm nhị phân (BST). Chúng tôi phải kiểm tra xem mỗi nút bên trong chỉ có một nút con hay không.
Vì vậy, nếu đầu vào giống như preorder =[22, 12, 13, 15, 14], thì đầu ra sẽ là True như BST giống như vậy -
Để giải quyết vấn đề này, chúng ta có thể làm theo một cách tiếp cận hiệu quả. Vì tất cả tàn tích của một nút nhỏ hơn hoặc lớn hơn, chúng ta có thể làm theo các bước sau -
-
Nhận người kế nhiệm đặt hàng trước tiếp theo của nút
-
Nhận người kế nhiệm đặt hàng trước cuối cùng của nút
-
Bây giờ, khi cả hai nút kế thừa nhỏ hơn hoặc lớn hơn nút hiện tại, hãy kiểm tra lại nếu không sẽ trả về false.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- tiếp theo:=0, cuối cùng:=0
- đối với tôi trong phạm vi từ 0 đến kích thước của đơn đặt hàng trước - 1, thực hiện
- next:=preorder [i] - preorder [i + 1]
- last:=preorder [i] - giá trị cuối cùng của preorder
- nếu tiếp theo * cuối cùng <0, thì
- trả về Sai
- trả về True
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
def solve(preorder): next = 0 last = 0 for i in range(len(preorder)-1): next = preorder[i] - preorder[i+1] last = preorder[i] - preorder[-1] if next * last < 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