Hello, I've solve the problem using hashmap (level of depth, TreeLinkNode). It got accepted, but i am not sure what constant extra space meant. I can also solve the problem using ArrayList instead of hashmap (a little less memory) using the same concept, keep the tail of each level and update to whatever comes next. If the solution is a tree with 5 levels, I would have 5 copies of tail for each level. Would this count as constant extra space?
I would be happy to share my solution, if anyone want to see.
'Constant extra space' usually means the solution containing several variables, the amount of them is not depend on what the input is.
You mentioned, you are using 'hashmap'. I would say this solution probably is not a constant extra space one.
Here is a flashstone's post, which presented how they make it O(1) space.