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

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

हल करने के चरण

• यदि रूट null है, तो False वापस करें
• यदि बायां और दायां सबट्री खाली हैं, तो true वापस करें जब sum - root.val = 0, अन्यथा false
• solve(root.left, sum - root.val) या solve(root.right, sum - 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