মনে করুন একটি BST এবং l, r দুটি বাউন্ড দেওয়া আছে। রুটে থাকা নোডগুলোর মধ্যে l এবং r (inclusive) রেঞ্জে কতগুলো নোড আছে সেটি গণনা করতে হবে।
উদাহরণস্বরূপ, l=7, r=13 হলে আউটপুট ৩ (৮, ১০, ১২)। ছবি দেওয়া আছে।
সমাধানের ধাপসমূহ
- stack := রুট দিয়ে স্ট্যাক, count := 0
- যখন stack খালি নয়,
- node := stack.pop()
- যদি node নন-নাল,
- যদি l <= node.data <= r, count++, stack-এ node.right, node.left পুশ করুন
- অন্যথায় যদি node.data < l, stack-এ node.right পুশ করুন
- অন্যথায়, stack-এ node.left পুশ করুন
- 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
