Google – Find Duplicated Subtrees

Related: Check if a Binary Tree contains duplicate subtrees of size 2 or more
Google – Find Duplicated Subtrees

Given a binary tree, return all duplicate subtrees.

For example,

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

The following are two duplicate subtrees:

      2
     /
    4

and

    4

Therefore, return [ [2,4], [4] ].

给一棵binary tree, 找出这个tree里有多少棵一样的subtree
[Solution]
思路是用string来表示一棵tree，并存在Set里用来检测duplicates。那么某个subtree的表示方法就是

String curr = dfs(root.left) + root.val + dfs(root.right)

但是特别要注意的是，null结点要用特殊符号来表示，比如#，否则没法唯一的确定数的结构。

class Solution {

  int cnt = 0;

  public int duplicatedSubtree(TreeNode root) {

    if (root == null) {

      return 0;

    }

    Set<String> trees = new HashSet<>();

    dfs(root, trees);

    return cnt;

  }

  private String dfs(TreeNode root, Set<String> trees) {

    if (root == null) {

      return "#";

    }

    String left = dfs(root.left, trees);

    String right = dfs(root.right, trees);

    String curr = left + root.val + right;

    if (trees.contains(curr)) {

      cnt++;

    }

    else {

      trees.add(curr);

    }

    return curr;

  }

}

https://discuss.leetcode.com/topic/19/find-duplicate-subtrees/12
Read full article from Google – Find Duplicated Subtrees