मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें सबसे लंबे पथ की लंबाई ढूंढनी है जो बाएं और दाएं चाइल्ड के बीच वैकल्पिक होता है और नीचे की ओर जाता है।
उदाहरण के लिए, यदि इनपुट इस तरह है:

तो आउटपुट 5 होगा क्योंकि वैकल्पिक पथ है [2, 4, 5, 7, 8]।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- यदि root नल है, तो
- 0 लौटाएं
- एक फ़ंक्शन dfs() परिभाषित करें। यह node, count, flag लेगा
- यदि node नल नहीं है, तो
- यदि flag, सत्य के समान है, तो
- a := dfs(node का बायाँ, count + 1, असत्य)
- b := dfs(node का दायाँ, 1, सत्य)
- अन्यथा जब flag, असत्य के समान है, तो
- a := dfs(node का दायाँ, count + 1, सत्य)
- b := dfs(node का बायाँ, 1, असत्य)
- a, b में से अधिकतम लौटाएं
- यदि flag, सत्य के समान है, तो
- count लौटाएं
- मुख्य विधि से निम्न करें:
- a := dfs(root का बायाँ, 1, असत्य)
- b := dfs(root का दायाँ, 1, सत्य)
- a, b में से अधिकतम लौटाएं
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
उदाहरण
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
class Solution:
def solve(self, root):
if not root:
return 0
def dfs(node, count, flag):
if node:
if flag == True:
a = dfs(node.left, count + 1, False)
b = dfs(node.right, 1, True)
elif flag == False:
a = dfs(node.right, count + 1, True)
b = dfs(node.left, 1, False)
return max(a, b)
return count
a = dfs(root.left, 1, False)
b = dfs(root.right, 1, True)
return max(a, b)
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.right = TreeNode(7)
root.right.left.right.left = TreeNode(8)
print(ob.solve(root))
इनपुट
root = TreeNode(2) root.left = TreeNode(3) root.right = TreeNode(4) root.right.left = TreeNode(5) root.right.right = TreeNode(6) root.right.left.right = TreeNode(7) root.right.left.right.left = TreeNode(8)
आउटपुट
5