Published: Sep 24, 2022
The traversing tree node is nothing special. Just going over by preorder traversal can visit all leaf nodes. The paths to the leaf nodes should be saved in the array. The key here is how to make the array back to the previous state when the traversal comes back from deeper level. One would be to pop the last element from path array. Another is to add the current root value when the traversal goes deeper level. Latter doesn’t need to pop the value.
rootof 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.
- The number of nodes in the tree is in the range
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
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: 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 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: 
The solution here didn’t took popping the last value from the path array. Instead, the solution doesn’t add the current value to the path array in the current level. Only when the traversal goes to deeper level, the root value is added to the path array. When it comes back to the upper level, the path array doesn’t have deeper level values. This way, we can create the path from root to leaf without add other paths.
# 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 = right class PathSumTwo: def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]: def helper(root, cur, result): if not root: return if not root.left and not root.right: if sum(cur) + root.val == targetSum: result.append(cur + [root.val]) return if root.left: helper(root.left, cur + [root.val], result) if root.right: helper(root.right, cur + [root.val], result) return result =  helper(root, , result) return result
O(n^2)– n: number of tree nodes
O(n + h)– h: height of the tree