পাইথনে বাইনারি ট্রির ম্যাক্সিমাম ডেপথ (Maximum Depth of Binary Tree)

একটি বাইনারি ট্রির সর্বোচ্চ গভীরতা (ডেপথ) বের করতে হবে। ডেপথ হল রুট থেকে লিফ পর্যন্ত সবচেয়ে লম্বা পথে নোডের সংখ্যা। রিকারসিভ পদ্ধতিতে সমাধান।

সমাধানের পদ্ধতি

1. রিকারসিভ ফাংশন solve(root, depth=0) লিখুন।
2. যদি রুট নাল হয়, depth রিটার্ন করুন।
3. অন্যথায় max(solve(root.left, depth+1), solve(root.right, depth+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

class Solution(object):
    def maxDepth(self, root):
        return self.solve(root)

    def solve(self, root, depth=0):
        if root is None:
            return depth
        return max(self.solve(root.left, depth + 1), self.solve(root.right, depth + 1))

tree1 = make_tree([1,2,2,3,4,None,3])
ob1 = Solution()
print(ob1.maxDepth(tree1))

ইনপুট

tree1 = make_tree([1,2,2,3,4,None,3])

আউটপুট

3