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
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
.
When I met this question, I intuitively come out that recursion may be a good way to solve this problem. For a recursive solution, the base case is extremely important and it is always the key point to solve a question.
Depend on my experience, for a tree question, the root==null is always a base case, another base case in this question is decided when the node is a leaf node. Then we know that we can use root.left==null && root.right==null to represent this situation and it also should be a base case here.
Once I found the base cases, we can just apply the DFS to track each path from root to leaf and update the sum variable.
The reason I use an array to hold the same value is because Java can only passed by value. For example,
in a=1;
void calculate(int a){
a=a+1;
}
System.out.println(a); // the result is still 1 , not 2
In order to track sum value of each calculation and not return the value of sum, we should use a collection or a wrapper class to hold it
So I use an array here to hold this sum value. If you anybody has another way to solve this problem, please leave a comment for me.
No comments:
Post a Comment