Finding all duplicate subtrees in one pass

This is an interesting problem: finding all the duplicate subtrees. N=10^4, so anything N^2 is intractable. There is an interesting idea:

1/ Perform a post-order DFS (remember: post-order means left -> right -> current node)

2/ As you're going up in the tree, attach a unique hash to the node based on the structure of the subtree. Now this is the part that takes a while to figure out. What I did that work for me is a simple calculation:

        BigInteger hash = (node.val + 207) * (left + 2007) * (right + 20007);

The reason that I add a number greater than 200 is to avoid negative numbers (the range of the values are -200 to 200)

3/ Notice that this way two identical subtrees will have the same hash. If you find it, make sure to flag it to be added later on to the return value.

That's it. Took me several attempts, but in the end it worked. Code is down below, cheers, ACC.

Find Duplicate Subtrees - LeetCode

652. Find Duplicate Subtrees

Medium

Given the root of a binary tree, return all duplicate subtrees.

For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with the same node values.

 

Example 1:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

Example 2:

Input: root = [2,1,1]
Output: [[1]]

Example 3:

Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]

 

Constraints:

• The number of the nodes in the tree will be in the range [1, 10^4]
• -200 <= Node.val <= 200

Accepted

128,621

Submissions

233,335

public IList FindDuplicateSubtrees(TreeNode root)

{
    Hashtable uniqueHash = new Hashtable();
    UniqueHashPostOrderDFS(root, uniqueHash);

    List retVal = new List();
    foreach (BigInteger key in uniqueHash.Keys)
    {
        TreeCount treeCount = (TreeCount)uniqueHash[key];
        if (treeCount.count > 1) retVal.Add(treeCount.node);
    }

    return retVal;
}

public BigInteger UniqueHashPostOrderDFS(TreeNode node, Hashtable uniqueHash)
{
    if (node == null) return 0;

    BigInteger left = UniqueHashPostOrderDFS(node.left, uniqueHash);
    BigInteger right = UniqueHashPostOrderDFS(node.right, uniqueHash);

    BigInteger hash = (node.val + 207) * (left + 2007) * (right + 20007);
    if (!uniqueHash.ContainsKey(hash)) uniqueHash.Add(hash, new TreeCount(node, 1));
    else
    {
        TreeCount treeCount = (TreeCount)uniqueHash[hash];
        treeCount.count++;
    }
    return hash;
}

public class TreeCount
{
    public TreeNode node = null;
    public int count = 0;

    public TreeCount(TreeNode node, int count)
    {
        this.node = node;
        this.count = count;
    }
}