129 Sum Root to Leaf Numbers
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
@tag-tree

Algorithm

Use DFS recursion to solve this problem because it is not simply adding the numbers of each node, but every time a new child node is encountered, the number of the parent node must be multiplied by 10 times and then added to next recursion.

If traversing to the leaf node, return the current accumulation result sum. If not, call the recursive function on its left and right child nodes respectively, and add the two results to return.