Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
Example 2:
Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There are two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.
Example 3:
Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.
Constraints:
The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
Solutions
Solution 1: Recursion
Starting from the root node, recursively traverse the tree and update the value of the node to the path sum from the root node to that node. When you traverse to a leaf node, determine whether this path sum is equal to the target value. If it is equal, return true, otherwise return false.
The time complexity is $O(n)$, where $n$ is the number of nodes in the binary tree. Each node is visited once.
1 2 3 4 5 6 7 8 91011121314151617
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defhasPathSum(self,root:Optional[TreeNode],targetSum:int)->bool:defdfs(root,s):ifrootisNone:returnFalses+=root.valifroot.leftisNoneandroot.rightisNoneands==targetSum:returnTruereturndfs(root.left,s)ordfs(root.right,s)returndfs(root,0)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funchasPathSum(root*TreeNode,targetSumint)bool{vardfsfunc(*TreeNode,int)booldfs=func(root*TreeNode,sint)bool{ifroot==nil{returnfalse}s+=root.Valifroot.Left==nil&&root.Right==nil&&s==targetSum{returntrue}returndfs(root.Left,s)||dfs(root.Right,s)}returndfs(root,0)}