ধরুন আমাদের একটি শিকড়যুক্ত বাইনারি গাছ আছে, আমাদের তার গভীরতম পাতার সর্বনিম্ন সাধারণ পূর্বপুরুষ ফেরত দিতে হবে। আমাদের মনে রাখতে হবে যে −
-
একটি বাইনারি গাছের নোড হল একটি পাতার নোড যদি এবং শুধুমাত্র যদি এটির কোন সন্তান না থাকে
-
গাছের মূলের গভীরতা 0, এবং যখন একটি নোডের গভীরতা d হয়, তখন এর প্রতিটি সন্তানের গভীরতা হয় d+1৷
-
নোড A-তে নোডের একটি সেট S-এর সর্বনিম্ন সাধারণ পূর্বপুরুষ যেখানে বৃহত্তম গভীরতা যেমন S-এর প্রতিটি নোড মূল A সহ সাবট্রিতে রয়েছে।
যদি ইনপুট হয় [1,2,3,4,5],
তাহলে আউটপুট হবে [2,4,5]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
সমাধান() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি নোড নেবে, এটি নিম্নরূপ কাজ করবে -
-
যদি নোড উপস্থিত না থাকে, তাহলে [0, None]
সহ একটি তালিকা ফেরত দিন -
যদি বাম এবং ডান সাবট্রি নোড থেকে খালি থাকে, তাহলে [1, None] সহ একটি তালিকা ফেরত দিন
-
d1, l :=সমাধান (নোডের বামে), d2, r :=সমাধান (নোডের ডানদিকে)
-
যদি d1> d2 হয়, তাহলে [d1 + 1, l]
মান সহ একটি তালিকা ফেরত দিন -
অন্যথায় যখন d2> d1, তারপর মান সহ একটি তালিকা ফেরত দিন [d2 + 1, r]
-
[d1 + 1, নোড]
মান সহ একটি তালিকা ফেরত দিন -
মূল পদ্ধতিতে, আমরা −
সম্পাদন করব -
তালিকা :=সমাধান(রুট)
-
ফেরত তালিকা[1]
উদাহরণ(পাইথন)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if data is not None: temp.left = TreeNode(data) else: temp.left = TreeNode(0) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data) else: temp.right = TreeNode(0) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree def print_tree(root): #print using inorder traversal if root is not None: print_tree(root.left) print(root.data, end = ', ') print_tree(root.right) class Solution(object): def lcaDeepestLeaves(self, root): return self.solve(root)[1] def solve(self,node): if not node: return [0,None] if not node.left and not node.right: return [1,node] d1,l = self.solve(node.left) d2,r = self.solve(node.right) if d1>d2: return [d1+1,l] elif d2>d1: return [d2+1,r] return [d1+1,node] ob = Solution() root = make_tree([1,2,3,4,5]) print_tree(ob.lcaDeepestLeaves(root))
ইনপুট
[1,2,3,4,5]
আউটপুট
4, 2, 5,