Find Duplicate Subtrees LeetCode solution in Java

1
/**
2
 * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode
3
 * right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left,
4
 * TreeNode right) { this.val = val; this.left = left; this.right = right; } }
5
 */
6
class Solution {
7
  public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
8
    List<TreeNode> list = new ArrayList<TreeNode>();
9
    HashSet<String> hashes = new HashSet<String>();
10
    HashSet<String> added = new HashSet<String>();
11

12
    // for each node, perform a dfs traversal and generate a hash
13
    // check if the hash already exists in a set,
14
    // if it does, get the treenode and add it to the list
15
    Stack<TreeNode> s = new Stack<TreeNode>();
16

17
    s.add(root);
18
    while (!s.isEmpty()) {
19
      TreeNode tmp = s.pop();
20
      dfs(tmp, "", tmp, list, hashes, added);
21

22
      if (tmp.left != null) {
23
        s.add(tmp.left);
24
      }
25
      if (tmp.right != null) {
26
        s.add(tmp.right);
27
      }
28
    }
29

30
    return list;
31
  }
32

33
  public void dfs(
34
      TreeNode parent,
35
      String hash,
36
      TreeNode root,
37
      List<TreeNode> list,
38
      HashSet<String> set,
39
      HashSet<String> added) {
40

41
    Stack<TreeNode> stack = new Stack<TreeNode>();
42

43
    stack.add(root);
44
    // String hash = "";
45
    hash += root.val + "ROOT,";
46
    while (!stack.isEmpty()) {
47
      TreeNode tmp = stack.pop();
48
      // hash += tmp.val + ",";
49

50
      if (tmp.left != null) {
51
        hash += tmp.left.val + "L,";
52
        stack.add(tmp.left);
53
      } else {
54
        hash += "NULLL,";
55
      }
56
      if (tmp.right != null) {
57
        hash += tmp.right.val + "R,";
58
        stack.add(tmp.right);
59
      } else {
60
        hash += "NULLR,";
61
      }
62
      if (tmp.left == null && tmp.right == null && stack.isEmpty()) {
63
        if (set.contains(hash)) {
64
          if (!added.contains(hash)) {
65
            list.add(parent);
66
            added.add(hash);
67
          }
68
        } else {
69
          set.add(hash);
70
        }
71
        return;
72
      }
73
    }
74
  }
75
}