পাইথনে বাইনারি ট্রি ম্যাক্সিমাম পাথ সাম

ধরুন একটি নন-এম্পটি বাইনারি ট্রি আছে। আমাদের পাথ সাম বের করতে হবে। এখানে পাথ বলতে কোনো স্টার্টিং নোড থেকে যেকোনো নোড পর্যন্ত প্যারেন্ট-চাইল্ড কানেকশনযুক্ত নোড সিকোয়েন্স বোঝায়। পাথে কমপক্ষে একটি নোড থাকতে হবে এবং রুটের মধ্য দিয়ে যাওয়ার প্রয়োজন নেই।

আউটপুট হবে ৩২।

সমাধানের ধাপগুলো −

solve() মেথড সংজ্ঞায়িত করুন যা node নেবে
যদি node null হয় অথবা node.data == 0 হলে 0 রিটার্ন করুন
left := max(0, solve(node.left)); right := max(0, solve(node.right))
ans := max(ans, left + right + node.data)
node.data + max(left, right) রিটার্ন করুন
মূল মেথড থেকে ans := -inf সেট করে solve(root) কল করুন এবং ans রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন −

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 maxPathSum(self, root):
        self.ans = -float('inf')
        self.solve(root)
        return self.ans
    def solve(self,node):
        if not node or node.data == 0:
            return 0
        left = max(0,self.solve(node.left))
        right = max(0,self.solve(node.right))
        self.ans = max(self.ans,left+right+node.data)
        return node.data + max(left,right)

ob = Solution()
root = make_tree([-10,9,10,None,None,15,7])
print(ob.maxPathSum(root))

ইনপুট

[-10,9,10,None,None,15,7]