মান ল করুন k এবং একটি বাইনারি সার্চ ট্রি, যেখানে প্রতিটি নোড হয় একটি লিফ নোড বা ২টি চাইল্ড ধারণ করে। আমাদের k মান ধারণকারী নোডটি খুঁজে বের করতে হবে এবং তার সিবলিং নোডের মান ফেরত দিতে হবে।
যদি ইনপুট নিচের মতো হয়:
k = 4, তখন আউটপুট হবে 10।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
একটি util() ফাংশন সংজ্ঞায়িত করুন। এটি root, k, ans গ্রহণ করবে।
যদি root-এর বাম এবং ডান দুটি চাইল্ড null না হয়, তবে ফেরত দিন।
যদি k > root-এর মান হয়, তবে:
যদি root-এর ডান চাইল্ডের মান k-এর সমান হয়, তবে root-এর বাম চাইল্ডের মান ans-এ যোগ করুন এবং ফেরত দিন।
অন্যথায়, util(root-এর ডান চাইল্ড, k, ans) কল করুন।
যদি k < root-এর মান হয়, তবে:
যদি root-এর বাম চাইল্ডের মান k-এর সমান হয়, তবে root-এর ডান চাইল্ডের মান ans-এ যোগ করুন এবং ফেরত দিন।
অন্যথায়, util(root-এর বাম চাইল্ড, k, ans) কল করুন।
মূল মেথড থেকে নিম্নলিখিত কাজ করুন:
ans := একটি নতুন তালিকা
util(root, k, ans) কল করুন
ans[0] ফেরত দিন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:
উদাহরণ
class TreeNode: def __init__(self, data, left = None, right = None): self.val = data self.left = left self.right = right def util(root, k, ans): if root.left is None and root.right is None: return if k > root.val: if root.right.val == k: ans.append(root.left.val) return else: util(root.right, k, ans) if k < root.val: if root.left.val == k: ans.append(root.right.val) return else: util(root.left, k, ans) class Solution: def solve(self, root, k): ans = [] util(root, k, ans) return ans[0] root = TreeNode(6) root.left = TreeNode(4) root.right = TreeNode(10) root.left.left = TreeNode(3) root.left.right = TreeNode(5) ob1 = Solution() print(ob1.solve(root, 4))
ইনপুট
root = TreeNode(6) root.left = TreeNode(4) root.right = TreeNode(10) root.left.left = TreeNode(3) root.left.right = TreeNode(5) 4
আউটপুট
10
