पायथन में पथ योग

मान लीजिए कि हमारे पास एक पेड़ और एक योग है। हमें एक रास्ता ऐसा खोजना होगा कि अगर हम उस रास्ते पर चलेंगे तो हमें वह योग मिलेगा जो दिए गए योग से मेल खाएगा। मान लीजिए पेड़ [0,-3,9,-10, null,5] जैसा है और योग 14 है, तो एक पथ है 0 → 9 → 5

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

• यदि जड़ शून्य है, तो गलत लौटें

• यदि बाएँ और दाएँ सबट्री खाली हैं, तो सही होने पर वापस लौटें - root.val =0, अन्यथा असत्य

• हल करें (रूट.बाएं, योग - root.val) या हल करें (रूट.दाएं, योग - root.val)

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

उदाहरण

# Definition for a binary tree node.
class TreeNode(object):
   def __init__(self, x):
      self.data = x
      self.left = None
      self.right = None
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution(object):
   def hasPathSum(self, root, sum):
      """
      :type root: TreeNode
      :type sum: int
      :rtype: bool
      """
      if not root :
         return False
      if not root.left and not root.right and root.data is not None:
         return sum - root.data == 0
      if root.data is not None:
         return self.hasPathSum(root.left, sum-root.data) or self.hasPathSum(root.right, sum-root.data)
tree1 = make_tree([0,-3,9,-10,None,5])
ob1 = Solution()
print(ob1.hasPathSum(tree1, 14))

इनपुट

tree1 = make_tree([0,-3,9,-10,None,5])

आउटपुट

True