Tổng đường dẫn bằng Python

Giả sử chúng ta có một cây và một tổng. Chúng ta phải tìm một con đường sao cho nếu chúng ta đi theo con đường đó, chúng ta sẽ nhận được tổng sẽ phù hợp với tổng đã cho. Giả sử cây giống như [0, -3,9, -10, null, 5] và tổng là 14, thì có một đường dẫn 0 → 9 → 5

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau.

• Nếu gốc là null, thì trả về False

• nếu cây con bên trái và bên phải trống, thì trả về true khi sum - root.val =0, ngược lại là false

• trả về giải quyết (root.left, sum - root.val) hoặc giải quyết (root.right, sum - root.val)

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

Ví dụ

# 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))

Đầu vào

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

Đầu ra

True