Find Duplicate Subtrees


  • 0

    Click here to see the full article post


  • 0
    N

    Can you briefly explain the lambda "x-> t++" in map.computeIfAbsent() please?


  • 0

    @Nio int uid = trees.computeIfAbsent(serial, x-> t++) means something like:

    if serial is not contained in trees, then trees.put(serial, t++) [make the value of this key serial equal to t, and then incremement t]

    and after, uid = trees.get(serial).


  • 0
    C

    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.


  • 0
    J

    I think the first solution is also O(N), why O(N ^ 2)


  • 0

    @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.


  • 0
    J

    @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.


  • 0

    @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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.