Kiểm tra xem mảng có biểu diễn thứ tự inorder của cây tìm kiếm nhị phân hay không trong Python

Giả sử chúng ta có một mảng các số gọi là nums. Cần kiểm tra xem mảng này có chứa các phần tử của một cây tìm kiếm nhị phân (BST) theo thứ tự duyệt inorder hay không.

Ví dụ, nếu đầu vào là nums = [5, 8, 15, 18, 20, 26, 39], thì đầu ra sẽ là True vì đây là thứ tự inorder của một BST.

Các bước giải quyết:

• size := kích thước của nums.
• Nếu size là 0 hoặc 1, trả về True.
• Duyệt i từ 1 đến size - 1:
  • Nếu nums[i-1] > nums[i], trả về False (không tăng dần).
• Trả về True.

Xem ví dụ dưới đây để hiểu rõ hơn:

Ví dụ

def solve(nums):
    size = len(nums)
    if size == 0 or size == 1:
        return True
    for i in range(1, size):
        if nums[i - 1] > nums[i]:
            return False
    return True

nums = [5, 8, 15, 18, 20, 26, 39]
print(solve(nums))

Đầu vào

[5, 8, 15, 18, 20, 26, 39]

Đầu ra

True