This time, return every root to leaf path whose values add up to the target. Each path is a list of node values.
DSA Animator › DSA Revision › Tree › Path Sum II
Remember: add on the way down, remove on the way back up. Only copy the path when you actually save it. The video solves Path Sum II (LeetCode 113, Medium) with the DFS Backtracking pattern from the Tree topic, and you can replay every step in the interactive Path Sum II animation.
This time, return every root to leaf path whose values add up to the target. Each path is a list of node values.
In the same tree with target 22, there are two paths. They are 5, 4, 11, 2 and 5, 8, 4, 5.
Copying the whole path at every node wastes memory and time. We can keep one shared path and undo each step on the way back.
Keep a path list and a remaining target. When you enter a node, add it to the path and subtract its value. At a leaf with remaining 0, save a copy of the path. When you leave a node, remove it from the path, which is the backtracking step.
Go down 5, 4, 11, 7, and the remaining is minus 5, so nothing is saved. Remove 7, and go to 2, where the remaining is 0, so save 5, 4, 11, 2. Back up to 5, and go right to 8, then the leaf 13, which leaves minus 4, so nothing is saved. Go to 4, then its left child 5 leaves exactly 0, so save 5, 8, 4, 5. The leaf 1 leaves 4, so nothing is saved. The answer has two paths.
In code, add the node value to the path, and subtract it from the target. If the node is a leaf and the target is 0, add a new copy of the path to the result. Otherwise recurse into the left and right child. Finally remove the last element of the path, so it's O of n squared in the worst case, because of the copies.
Remember: add on the way down, remove on the way back up. Only copy the path when you actually save it.