Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
Example 2:
Input: root = [1,2,3], targetSum = 5
Output: []
Example 3:
Input: root = [1,2], targetSum = 0
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
Solutions
Solution 1: DFS
We start from the root node, recursively traverse all paths from the root node to the leaf nodes, and record the path sum. When we traverse to a leaf node, if the current path sum equals targetSum, then we add this path to the answer.
The time complexity is $O(n^2)$, where $n$ is the number of nodes in the binary tree. The space complexity is $O(n)$.
1 2 3 4 5 6 7 8 91011121314151617181920212223
# 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:defpathSum(self,root:Optional[TreeNode],targetSum:int)->List[List[int]]:defdfs(root,s):ifrootisNone:returns+=root.valt.append(root.val)ifroot.leftisNoneandroot.rightisNoneands==targetSum:ans.append(t[:])dfs(root.left,s)dfs(root.right,s)t.pop()ans=[]t=[]dfs(root,0)returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcpathSum(root*TreeNode,targetSumint)(ans[][]int){t:=[]int{}vardfsfunc(*TreeNode,int)dfs=func(root*TreeNode,sint){ifroot==nil{return}s-=root.Valt=append(t,root.Val)ifroot.Left==nil&&root.Right==nil&&s==0{ans=append(ans,slices.Clone(t))}dfs(root.Left,s)dfs(root.Right,s)t=t[:len(t)-1]}dfs(root,targetSum)return}