Given a binary tree and a number
k, your task is to find the sum of tree nodes at level
k. The binary tree is represented by a string
tree with the format:
(<node-value>(<left subtree>)(<right subtree>)).
tree = "(0(5(6()())(14()(9()())))(7(1()())(23()())))" and
k = 2, the output should be
treeLevelSum(tree, k) = 44.
Explanation: The nodes at level
23, so the answer is
6 + 14 + 1 + 23 = 44.
- [time limit] 4000ms (py)
- [input] string tree
A valid string representing a tree.
2 ≤ tree.length ≤ 105.
All the values in a given tree are guaranteed to be integers.
- [input] integer k
0 ≤ k ≤ 105.
- [output] integer
The total sum of all the values at level
kin a tree.
What we need is to find where the level starts and ends. We can do this by counting the ‘(‘ and ‘)’s. Everytime we see a ‘(‘ we go one level deeper and ‘)’ goes back up. Then, if we are in the level we are looking for and the character is not a parenthesis, we count the number. Of course, if it is not a parenthesis, we need to make sure that we are storing the number correctly, it may be bigger than 1-digit numbers. So, we convert the chars to a number until we see a different character and add that to the sum. (This is to make sure we don’t add 2 and 3 to sum instead of 23).