पायथन में रूट टू लीफ पाथ में अपर्याप्त नोड्स

मान लीजिए कि हमारे पास एक बाइनरी ट्री है। एक नोड को अपर्याप्त के रूप में जाना जाता है यदि इस नोड को प्रतिच्छेद करने वाले प्रत्येक रूट से लीफ पथ में योग सीमा से सख्ती से कम है। हमें सभी अपर्याप्त नोड्स को एक साथ हटाना होगा, और परिणामी बाइनरी ट्री की जड़ को वापस करना होगा। तो अगर पेड़ की तरह है, और सीमा 1 है -

तब आउटपुट ट्री होगा -

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

• एक विधि को हल करें परिभाषित करें (), यह जड़ और सीमा लेगा
• यदि नोड में कोई बाएँ और दाएँ सबट्री नहीं है, तो
  • यदि रूट का मान 1 से कम है, तो शून्य लौटाएं, अन्यथा रूट करें
• यदि रूट ने सबट्री छोड़ दी है, तो रूट के बाएं:=हल करें (रूट के बाएं, सीमा - रूट का मान)
• यदि रूट में राइट सबट्री है, तो रूट का राइट:=सॉल्व (रूट का राइट, लिमिट - रूट का वैल्यू)
• यदि रूट में या तो लेफ्ट सबट्री, या राइट सबट्री या दोनों हैं, तो रूट को वापस करें, अन्यथा शून्य।

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

उदाहरण

class Solution(object):
   def sufficientSubset(self, root, limit):
      """
      :type root: TreeNode
      :type limit: int
      :rtype: TreeNode
      """
      if not root.left and not root.right:
         return None if root.val<limit else root
      if root.left:
         root.left= self.sufficientSubset(root.left,limit-root.val)
      if root.right:
         root.right = self.sufficientSubset(root.right,limit-root.val)
      return root if root.left or root.right else None

इनपुट

[1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14]
1

आउटपुट

[1,2,3,4,null,null,7,8,9,null,14]