ตรวจสอบว่าโหนดภายในของ BST มีลูกเพียงข้างเดียวจาก Preorder Traversal ใน Python

ปัญหา

ให้ Preorder traversal ของ BST ตรวจสอบว่า ทุกโหนดภายใน (internal node) มีลูกเพียงข้างเดียว (ไม่มีโหนดที่มีลูก 2 ข้าง)

ข้อสังเกตสำคัญ

ใน BST: โหนดซ้าย < โหนด < โหนดขวา
ถ้าโหนดมีลูก 2 ข้าง → จะมีค่าระหว่างโหนดปัจจุบันกับโหนดสุดท้ายใน preorder

อัลกอริทึม O(n)

1. สำหรับแต่ละโหนด preorder[i]:
   • next_diff = preorder[i] - preorder[i+1]
   • last_diff = preorder[i] - preorder[-1]
2. ถ้า next_diff * last_diff < 0 → โหนดมีลูก 2 ข้าง → False

ตัวอย่าง

preorder = [22, 12, 13, 15, 14] → ทุกโหนดมีลูกข้างเดียว → True

โค้ดตัวอย่าง

def solve(preorder):
    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

print(solve([22, 12, 13, 15, 14]))  # True
print(solve([8, 5, 10]))  # False (โหนด 8 มีลูก 2 ข้าง)

อินพุต / เอาต์พุต

Input:  [22, 12, 13, 15, 14]
Output: True