পাইথনে বাইনারি ট্রির দ্বিতীয় গভীরতম নোড নির্ণয়

একটি বাইনারি ট্রি দেওয়া আছে। দ্বিতীয় গভীরতম লিফ নোডের গভীরতা বের করতে হবে। যদি একাধিক গভীরতম লিফ থাকে তবে দ্বিতীয় গভীরতম পরবর্তী উন্নত লে ভেল হবে। রুটের গভীরতা ০।

উদাহরণ ট্রির আউটপুট ১, কারণ দ্বিতীয় গভীরতম নোড ৩।

সমাধানের ধাপসমূহ

লেভেল অর্ডার ট্রাভার্সাল (BFS) করুন
প্রতিটি লেভেলে লিফ নোড পাওয়া গেলে prev এবং now আপডেট করুন
সব লেভেল শেষে prev ফেরত দিন

উদাহরণ কোড

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):
        if root is None:
            return None
        nodes = []
        nodes.append(root)
        count = 0
        prev = 0
        now = 0
        while nodes:
            new = []
            flag = True
            for node in nodes:
                if flag and (not node.left) and (not node.right):
                    prev = now
                    now = count
                    flag = False
                if node.left:
                    new.append(node.left)
                if node.right:
                    new.append(node.right)
            nodes = new
            count += 1
        return prev

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)
root.right.right.right = TreeNode(8)
print(ob.solve(root))

ইনপুট

root = TreeNode(2) root.left = TreeNode(3) root.right = TreeNode(4) root.right.left = TreeNode(5) root.right.right = TreeNode(6) root.right.left.left = TreeNode(7) root.right.right.right = TreeNode(8)