652. Find Duplicate Subtrees

I like to make change on my post on leetcode.com discuss written over 8 months ago.

Here is the link.

C# post order traversal and use serialized string to help

Dec. 3, 2018
It is a medium level algorithm. I spent over an hour to write a solution but I came cross the time out issue. So I decided to study the discuss and then chose one of posts and implemented the solution. The experience to write my own code was very helpful, I had to fix the issue to separate left and right child issue.

Follow up on June 30, 2019
I like to add more detail in my post. In order for me to review the algorithm, I like to share my experience to solve the problem this time.

Here are highlights:

1. Post order traversal the tree, every node will be tracked its subtree, and the serialized subtree in string will be stored as key in a hashmap, root node is the value. The data structure can be in C# Dictionary<string, IList> or Dictionary<string, HashSet>;
2. More detail on step 1, how to serialize a tree using string? We can construct the string using each node using post order, and then use '(' as prefix and ')' as suffix for each node.
3. To return duplicate subtrees, we only need to return the root node of any node. So first node in the array can be selected. Hashset can be converted to an array first, and then first element is selected.

More detail as an interviewer
I like to ask the algorithm on interviewing.io as an interviewer, so I have to look into all kinds of ideas to solve the problem as well.

1. I like to prove that post order traversal will not bring ambiguity; How to prove that?
2. Preorder works against Leetcode online judge;
3. Inorder traversal does not work. The counter example is the following:
   
   The answer should be [[0]], but the code will return [[0],[0,0]].
4. The serialization of tree is related to 297 serialize and deserialize binary tree. The post order/ preorder traversal should work, but not inorder traversal.

Case study

null pointer using '+',
node with value is expressed using '(' + value +')' since two interger should be separated from each other.

Post order traversal

So based on the above analysis, the following two trees will not be mixed together.

Inorder traversal

So based on the above analysis, the following two trees will be mixed together.

Preorder traversal

Preorder traversal should be reversed from post order traversal

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public IList<TreeNode> FindDuplicateSubtrees(TreeNode root)
        {
            if (root == null)
            {
                return new List<TreeNode>();
            }

            var dict = new Dictionary<string, HashSet<TreeNode>>();            

            postorderTraverse(root, dict);

            var result = new List<TreeNode>(); 

            foreach (var pair in dict)
            {
                var set = pair.Value;
                if (set.Count > 1)
                {
                    var array = set.ToArray();
                    result.Add(array[0]);
                }
            }

            return result; 
        }

        private static string postorderTraverse(TreeNode root, Dictionary<string, HashSet<TreeNode>> visited)
        {
            if (root == null)
                return "+";            
            
            // make sure that it is post order traversal
            //                          Left                                   right               
            var serialized = postorderTraverse(root.left, visited) + postorderTraverse(root.right, visited) + "(" + root.val + ")";

            if (!visited.ContainsKey(serialized))
            {
                visited.Add(serialized, new HashSet<TreeNode>()); 
            }

            visited[serialized].Add(root);

            return serialized;
        }
}

If you like my analysis and sharing, please give me an upvote. I also put all my C# algorithm together, the link is
https://github.com/jianminchen/Leetcode_Julia/tree/master/Leetcode discussion.

Comments: 0

Best