मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें बाइनरी ट्री में सबसे लंबा पथ ढूंढना है।
इसलिए, यदि इनपुट इस तरह है
तो आउटपुट 5 होगा क्योंकि सबसे लंबा लगातार क्रम [2, 3, 4, 5, 6] है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- यदि रूट null है, तो
- 0 लौटाएं
- maxPath := 0
- helper() फ़ंक्शन परिभाषित करें। यह नोड लेगा
- inc := 1, dec := 1
- यदि नोड का बायां null नहीं है, तो
- [left_inc, left_dec] := helper(नोड का बायां)
- अन्यथा,
- [left_inc, left_dec] := [0, 0]
- यदि नोड का दायां null नहीं है, तो
- [right_inc, right_dec] := helper(नोड का दायां)
- अन्यथा,
- [right_inc, right_dec] := [0, 0]
- यदि नोड का बायां null नहीं है और नोड का मान - नोड के बाएं का मान 1 के समान है, तो
- inc := inc और (left_inc + 1) का अधिकतम
- अन्यथा जब नोड का बायां null नहीं है और नोड का मान - नोड के बाएं का मान -1 के समान है, तो
- dec := dec और (left_dec + 1) का अधिकतम
- यदि नोड का दायां null नहीं है और नोड का मान - नोड के दाएं का मान 1 के समान है, तो
- inc := inc और (right_inc + 1) का अधिकतम
- अन्यथा जब नोड का दायां null नहीं है और नोड का मान - नोड के दाएं का मान -1 के समान है, तो
- dec := dec और (right_dec + 1) का अधिकतम
- यदि नोड का बायां null नहीं है और नोड का दायां null नहीं है और नोड के बाएं का मान - नोड का मान 1 के समान है और नोड का मान - नोड के दाएं का मान 1 के समान है, तो
- maxPath := maxPath और (left_dec + right_inc + 1) का अधिकतम
- अन्यथा जब नोड का बायां null नहीं है और नोड का दायां null नहीं है और नोड के बाएं का मान - नोड का मान -1 के समान है, तो
- maxPath := maxPath और (left_inc + right_dec + 1) का अधिकतम
- maxPath := maxPath, inc और dec का अधिकतम
- inc, dec लौटाएं
- मुख्य मेथड से निम्नलिखित करें:
- helper(रूट)
- maxPath लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
def print_tree(root):
if root is not None:
print_tree(root.left)
print(root.val, end=', ')
print_tree(root.right)
class Solution:
def solve(self, root):
if not root:
return 0
self.maxPath = 0
def helper(node):
inc, dec = 1, 1
if node.left:
left_inc, left_dec = helper(node.left)
else:
left_inc, left_dec = 0, 0
if node.right:
right_inc, right_dec = helper(node.right)
else:
right_inc, right_dec = 0, 0
if node.left and node.val - node.left.val == 1:
inc = max(inc, left_inc + 1)
elif node.left and node.val - node.left.val == -1:
dec = max(dec, left_dec + 1)
if node.right and node.val - node.right.val == 1:
inc = max(inc, right_inc + 1)
elif node.right and node.val - node.right.val == -1:
dec = max(dec, right_dec + 1)
if (node.left and node.right and node.left.val - node.val == 1 and node.val - node.right.val == 1):
self.maxPath = max(self.maxPath, left_dec + right_inc + 1)
elif (node.left and node.right and node.left.val - node.val == -1 and node.val - node.right.val == -1):
self.maxPath = max(self.maxPath, left_inc + right_dec + 1)
self.maxPath = max(self.maxPath, inc, dec)
return inc, dec
helper(root)
return self.maxPath
ob = Solution()
root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(9)
root.right.left.left = TreeNode(6)
print(ob.solve(root))इनपुट
root = TreeNode(3) root.left = TreeNode(2) root.right = TreeNode(4) root.right.left = TreeNode(5) root.right.right = TreeNode(9) root.right.left.left = TreeNode(6)
आउटपुट
5
