Find Duplicate Subtrees


@Nio
int uid = trees.computeIfAbsent(serial, x> t++)
means something like:if
serial
is not contained intrees
, thentrees.put(serial, t++)
[make the value of this keyserial
equal tot
, and then incremementt
]and after,
uid = trees.get(serial)
.

@jocelynayoga
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.)@bhawna1712
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.

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.