अजगर में एक बाइनरी ट्री के सबसे लंबे क्रमागत पथ की लंबाई ज्ञात करने का कार्यक्रम

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें बाइनरी ट्री में सबसे लंबा रास्ता खोजना होगा।

तो, अगर इनपुट पसंद है

तो आउटपुट 5 होगा क्योंकि लगातार सबसे लंबा क्रम [2, 3, 4, 5, 6] है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

यदि रूट रिक्त है, तो
- वापसी 0
मैक्सपाथ:=0
एक फंक्शन हेल्पर () को परिभाषित करें। यह नोड लेगा
इंक:=1, दिसंबर:=1
यदि नोड का बायां भाग रिक्त नहीं है, तो
- [left_inc, left_dec] :=सहायक (नोड के बाएं)
अन्यथा,
- [left_inc, left_dec] :=[0, 0]
यदि नोड का अधिकार शून्य नहीं है, तो
- [right_inc, right_dec] :=हेल्पर (नोड के दाएं)
अन्यथा,
- [right_inc, right_dec] :=[0, 0]
यदि नोड का बायां भाग शून्य नहीं है और नोड का मान - नोड के बाएं का मान 1 के समान है, तो
- inc :=अधिकतम inc और (left_inc + 1)
अन्यथा जब नोड का बायां भाग शून्य नहीं होता है और नोड का मान - नोड के बाएं का मान -1 के समान होता है, तो
- दिसंबर:=अधिकतम दिसंबर और (बाएं_डेक + 1)
यदि नोड का अधिकार शून्य नहीं है और नोड का मान - नोड के अधिकार का मान 1 के समान है, तो
- inc :=अधिकतम inc और (right_inc + 1)
अन्यथा जब नोड का अधिकार शून्य नहीं है और नोड का मान - नोड के अधिकार का मान -1 के समान है, तो
- दिसंबर:=अधिकतम दिसंबर और (right_dec + 1)
यदि नोड का बायां भाग शून्य नहीं है और नोड का दायां शून्य नहीं है और नोड के बाएं का मान - नोड का मान 1 के समान है और नोड का मान - नोड के दाएं का मान 1 के समान है, तो
- maxPath :=maxPath का अधिकतम और (left_dec + right_inc + 1)
अन्यथा जब नोड का बायां नोड शून्य नहीं है और नोड का दायां शून्य नहीं है और नोड के बाएं का मान - नोड का मान -1 के समान है, तो
- maxPath :=maxPath का अधिकतम और (left_inc + right_dec + 1)
maxPath :=maxPath, inc और dec का अधिकतम
रिटर्न इंक, दिसंबर
मुख्य विधि से निम्न कार्य करें:
सहायक (रूट)
मैक्सपाथ लौटाएं

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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)