Click here to see the full article post
int uid = trees.computeIfAbsent(serial, x-> t++) means something like:
serial is not contained in
trees.put(serial, t++) [make the value of this key
serial equal to
t, and then incremement
uid = trees.get(serial).
Would you please explain how the second approach runs in O(n) and first in O(n square). Isn't it same as Approach 1 except the fact that we are using two hash tables and the key for second hash table is an integer instead of string.
In the first solution, every node creates a serialization of it's subtree, which is going to be quite large and take O(N) work per node (and there are N nodes.)
In the second solution, every node only creates a sort of pointer (val, left, right) which takes O(1) work and is significantly smaller.
@awice but in both solutions, you need to call
String serial = node.val + "," + lookup(node.left) + "," + lookup(node.right);
which is the same. In the first solution, every node does not construct the string independently, it still visit each node once.
@jocelynayoga String concatenation is linear time, so creating such a string with length L is O(L). The expected length of each serial is O(N).
For a concrete example, imagine the tree is just a line (every node has a left child except one leaf). Then the serials are like "A", "BA", "CBA", "DCBA", .... . Creating all of these is O(N^2) work.
does this String serial = node.val + "," + lookup(node.left) + "," + lookup(node.right) take O(n)? It looks like both approach would require running this for every node. so both approach would take O(N2).
Both these two solution use a similar recursive structure, the difference is just that the first solution returns string(which could be quite long) while the second returns a uid number. Hence both solution takes O(N) time, and the first takes O(N^2) space while the second takes O(N) space.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.