The first solution has time complexity of O(n^2) and space complexity of O(n). For each root, we’ll call recursively until reaching the bottom of the tree and start adding back. The tree would be n nodes tall in the worst case scenario so for each root the TC is O(n) and for n roots it’s O(n^2). Space wise, in the worst case scenario we need O(n) for the recursive stack.
The second solution has time complexity of O(n) and space complexity of O(n). The first run is the same as the first solution, in O(n) time we have the result for the first root. Since all possible outcomes for list length in [1, n-1] have been encountered and stored in the hashmap. For each of the following roots we only need to multiply 2 values from the hashmap which takes O(1). So overall it’s O(n) + (n-1)O(1) which is O(n). Space wise, O(n) is needed for the hashmap.