สมมติว่ามี BST และมีขอบเขตซ้ายและขวา l และ r เราต้องนับโหนดทั้งหมดที่มีค่าอยู่ระหว่าง l และ r (รวม)
เช่น ถ้าอินพุตเป็นต้นไม้ดังภาพ l = 7, r = 13 ผลลัพธ์จะเป็น 3 โหนดคือ 8, 10, 12
ขั้นตอนการแก้ปัญหา
- stack := สแต็ก ใส่ root ไว้ก่อน count := 0
- while stack ไม่ว่าง
- node := ดึงข้อมูลบนสุดของ stack
- ถ้า node ไม่ใช่ null
- ถ้า l <= node.data <= r count := count + 1, stack ใส่ right และ left ของ node
- ถ้า node.data < l stack ใส่ right ของ node
- มิฉะนั้น stack ใส่ left ของ node
- คืนค่า count
ตัวอย่างโค้ด
from collections import deque
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
class Solution:
def solve(self, root, 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 < l:
stack += [node.right]
else:
stack += [node.left]
return count
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root, 7, 13))
อินพุต
root = TreeNode(12) root.left = TreeNode(8) root.right = TreeNode(15) root.left.left = TreeNode(3) root.left.right = TreeNode(10) 7,13
เอาต์พุต
3
