Given a binary tree and a target and , Determine whether there is a path from root node to leaf node in the tree , The sum of the values of all nodes in this path is equal to the target and .
explain : A leaf node is a node that has no children .
Example :
Given the following binary tree , And goals and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, Because there are goals and for 22 The path from the root node to the leaf node 5->4->11->2.
Recursion , When root by None when , return False, When root The value is equal to the sum And root When it is a leaf node , return true, If it's not equal , Recursion down , As long as the left and right subtrees have a path, you can return to True
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if root == None:
return False
if root.val == sum and root.left == None and root.right == None:
return True
return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)