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