पायथन में एक बाइनरी ट्री के सबसे लंबे वैकल्पिक पथ की लंबाई खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी ट्री है, हमें सबसे लंबा रास्ता खोजना है जो बाएं और दाएं बच्चे और नीचे जाने के बीच वैकल्पिक हो।

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

तो आउटपुट 5 होगा क्योंकि वैकल्पिक पथ [2, 4, 5, 7, 8] है।

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

यदि रूट रिक्त है, तो
- वापसी 0
एक फ़ंक्शन को परिभाषित करें dfs() । यह नोड, गिनती, ध्वज लेगा
यदि नोड रिक्त नहीं है, तो
- यदि ध्वज सत्य के समान है, तो
  - a :=dfs (नोड के बाएं, गिनती + 1, गलत)
  - b :=dfs (नोड का दायां, 1, सही)
- अन्यथा जब ध्वज असत्य के समान हो, तब
  - a :=dfs (नोड के दाएं, गिनती + 1, सही)
  - b :=dfs (नोड के बाएं, 1, गलत)
- अधिकतम a, b लौटाएं
वापसी की संख्या
मुख्य विधि से निम्न कार्य करें:
a :=dfs (रूट के बाएँ, 1, असत्य)
b :=dfs (रूट का दायां, 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)