โปรแกรมค้นหาจำนวนโหนดในช่วงใน Python

สมมติว่าเรามี BST และเรายังมีขอบเขตซ้ายและขวา l และ r เราต้องหาจำนวนโหนดทั้งหมดในรูทที่มีค่าอยู่ระหว่าง l และ r (รวม)

ดังนั้นหากอินพุตเป็นแบบ

l =7, r =13 จากนั้นผลลัพธ์จะเป็น 3 เนื่องจากมีสามโหนด:8, 10, 12

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

• stack :=a stack และใส่ root ในตอนแรก นับ :=0

• ในขณะที่สแต็กไม่ว่างเปล่าให้ทำ

  • โหนด :=องค์ประกอบด้านบนของสแต็กและองค์ประกอบป๊อป

  • ถ้าโหนดไม่เป็นโมฆะ

    • ถ้า l <=ข้อมูลของโหนด <=r แล้ว

      • นับ :=นับ + 1

      • stack :=กดไปทางขวาของโหนดและด้านซ้ายของโหนดลงใน stack

    • มิฉะนั้นเมื่อข้อมูลของโหนด

      • stack :=กดขวาของโหนดลงใน stack

      • มิฉะนั้น

      • stack :=ดันซ้ายของโหนดไปยัง stack

• จำนวนคืน

ตัวอย่าง

จากคอลเลกชันที่นำเข้า dequeclass TreeNode:def __init__(self, data, left =None, right =None):self.data =data self.left =left self.right =rightclass วิธีแก้ไข:def แก้ปัญหา (ตนเอง, รูท, l , r):stack, count =[root], 0 while stack:node =stack.pop() if node:if l <=node.data <=r:count +=1 stack +=[node.right, node .left] elif node.data  
อินพุต
 
root =TreeNode(12)root.left =TreeNode(8)root.right =TreeNode(15)root.left.left =TreeNode(3)root.left.right =TreeNode(10)7,13 
ผลลัพธ์
 
3