बाइनरी ट्री में सबसे लंबा पथ खोजने के लिए फ़ंक्शन

Python Hard functions

कार्य «बाइनरी ट्री में सबसे लंबा पथ खोजने के लिए फ़ंक्शन»

एक बाइनरी ट्री दिया गया है, जिसके प्रत्येक नोड में एक पूर्णांक है। रूट से लीफ तक के पथ पर मानों का अधिकतम योग ज्ञात करना आवश्यक है। पथ रूट से शुरू होकर लीफ पर समाप्त होना चाहिए। एक फ़ंक्शन max_path_sum(root) लिखें, जो ट्री के रूट को स्वीकार करता है और अधिकतम योग लौटाता है। ट्री को एक सूची के रूप में दिया गया है, जहाँ -1 का अर्थ नोड की अनुपस्थिति है। सीमाएँ: नोड्स की संख्या 1000 से अधिक नहीं है, नोड्स के मान -1000 से 1000 तक हैं।

इनपुट प्रारूप

पहली पंक्ति में एक पूर्णांक n है — नोड्स की संख्या। दूसरी पंक्ति में n पूर्णांक रिक्त स्थान से अलग किए गए हैं — चौड़ाई में ट्रैवर्सल के क्रम में नोड्स के मान (स्तर दर स्तर), जहाँ -1 का अर्थ खाली नोड है।

आउटपुट प्रारूप

एक पूर्णांक — जड़ से पत्ती तक के पथ पर अधिकतम योग।

उदाहरण

उदाहरण 1

इनपुट

5
-1 2 3 -1 -1

आउटपुट

2

main.py