मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें रूट नोड से लीफ नोड तक जाने वाले किसी भी पथ का सबसे बड़ा योग ढूंढना है।
उदाहरण के लिए, यदि इनपुट जैसा है:
तो आउटपुट 29 होगा क्योंकि रूट से, यदि हम पथ 5-<9-<7-<8 का पालन करते हैं तो जोड़ के बाद यह 29 होगा।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
- walk() फंक्शन परिभाषित करें जो node, s लेता है:
- यदि node null है, तो max_sum := max(max_sum, s), वापस करें
- s := s + node का डेटा
- walk(node का बायां, s)
- walk(node का दायां, s)
- मुख्य विधि से:
- max_sum := 0
- walk(root, 0)
- max_sum वापस करें
उदाहरण
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
class Solution:
def walk(self, node, s):
if not node:
self.max_sum = max(self.max_sum, s)
return
s += node.data
self.walk(node.left, s)
self.walk(node.right, s)
def solve(self, root):
self.max_sum = 0
self.walk(root, 0)
return self.max_sum
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))
इनपुट
root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8)
आउटपुट
29