ตรวจสอบว่าแต่ละโหนดภายในของ BST มีลูกหนึ่งคนใน Python . หรือไม่

สมมติว่าเรามีการสั่งซื้อล่วงหน้าผ่านเส้นทางการค้นหาแบบไบนารี (BST) เราต้องตรวจสอบว่าแต่ละโหนดภายในมีลูกเพียงคนเดียวหรือไม่

ดังนั้น หากอินพุตเป็นเหมือนการสั่งซื้อล่วงหน้า =[22, 12, 13, 15, 14] ผลลัพธ์จะเป็น True เนื่องจาก BST เป็นเช่นนั้น -

เพื่อแก้ปัญหานี้ เราสามารถปฏิบัติตามแนวทางที่มีประสิทธิภาพวิธีหนึ่ง เนื่องจาก decedent ทั้งหมดของโหนดมีขนาดเล็กกว่าหรือใหญ่กว่า เราสามารถทำตามขั้นตอนเหล่านี้ได้ -

• รับตัวต่อจากการสั่งซื้อล่วงหน้าครั้งถัดไปของโหนด

• รับตัวต่อจากการสั่งซื้อล่วงหน้าครั้งสุดท้ายของโหนด

• ตอนนี้เมื่อตัวตายตัวแทนทั้งคู่น้อยกว่าหรือมากกว่าโหนดปัจจุบัน ให้ตรวจสอบอีกครั้ง ไม่เช่นนั้นจะคืนค่าเท็จ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถัดไป :=0, สุดท้าย :=0
• สำหรับ i ในช่วง 0 ถึงขนาดของการสั่งซื้อล่วงหน้า - 1 ทำ
  • ถัดไป :=สั่งซื้อล่วงหน้า[i] - สั่งซื้อล่วงหน้า[i+1]
  • last :=preorder[i] - ค่าสุดท้ายของการสั่งซื้อล่วงหน้า
  • ถ้าถัดไป * สุดท้าย <0 แล้ว
    • คืนค่าเท็จ
• คืนค่า True

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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))

อินพุต

[22, 12, 13, 15, 14]

ผลลัพธ์

True