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

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

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

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

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

उत्तर :=0
फ़ंक्शन ढूंढें() को परिभाषित करें। यह नोड लेगा
यदि नोड शून्य है, तो
- वापसी (-1, -1)
leftCnt :=खोज का अधिकतम लौटाया गया मान (नोड के बाईं ओर) + 1
rightCnt :=खोज का अधिकतम लौटाया गया मान (नोड का दायां) + 1
यदि नोड का मान सम है, तो
- उत्तर:=अधिकतम उत्तर और (बाएंCnt + दाएँCnt + 1)
- वापसी (बाएं सीएनटी, दाएं सीएनटी)
अन्यथा,
- उत्तर:=अधिकतम उत्तर, बाएँCnt और दाएँCnt
- वापसी (-1, -1)
मुख्य विधि से निम्न कार्य करें -
ढूंढें (रूट)
वापसी उत्तर

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

उदाहरण

class TreeNode:
   def __init__(self, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      ans = 0
      def find(node):
         nonlocal ans
         if not node:
            return -1, -1
         leftCnt = max(find(node.left)) + 1
         rightCnt = max(find(node.right)) + 1
         if node.val % 2 == 0:
            ans = max(ans, leftCnt + rightCnt + 1)
            return leftCnt, rightCnt
         else:
            ans = max(ans, max(leftCnt, rightCnt))
            return -1, -1
      find(root)
      return ans
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root))

इनपुट

root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)