aboutsummaryrefslogtreecommitdiff
path: root/find_duplicate_subtree.c
diff options
context:
space:
mode:
Diffstat (limited to 'find_duplicate_subtree.c')
-rw-r--r--find_duplicate_subtree.c59
1 files changed, 59 insertions, 0 deletions
diff --git a/find_duplicate_subtree.c b/find_duplicate_subtree.c
new file mode 100644
index 0000000..a8ac477
--- /dev/null
+++ b/find_duplicate_subtree.c
@@ -0,0 +1,59 @@
+// 652. Find Duplicate Subtrees
+#include "./lib/uthash/src/uthash.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/*
+ * given 'root' of a binary tree, return all duplicate subtrees. for each kind
+ * of duplicate, only return the root node of any one of them. two trees are
+ * duplicate if they have the same structure with the same node values.
+ */
+
+struct TreeNode {
+ int val;
+ struct TreeNode *left;
+ struct TreeNode *right;
+};
+
+typedef struct {
+ char *r_key;
+ int cnt;
+ UT_hash_handle hh;
+} h_elem;
+
+char *dfs(struct TreeNode *root, h_elem **map, struct TreeNode **ans,
+ int *idx) {
+ h_elem *tmp;
+ if (!root) {
+ char *r = calloc(sizeof(char), 2);
+ strcpy(r, "N");
+ return r;
+ }
+ char *l_str = dfs(root->left, map, ans, idx);
+ char *r_str = dfs(root->right, map, ans, idx);
+ int c_len = strlen(l_str) + strlen(r_str) + 7;
+ char *ans_str = calloc(sizeof(char), c_len);
+ sprintf(ans_str, "%d, %s, %s\n", root->val, l_str, r_str);
+ HASH_FIND_STR(*map, ans_str, tmp);
+ if (tmp) {
+ tmp->cnt++;
+ if (tmp->cnt == 2)
+ ans[(*idx)++] = root;
+ } else {
+ h_elem *tmp = malloc(sizeof(h_elem));
+ tmp->r_key = ans_str;
+ tmp->cnt = 1;
+ HASH_ADD_KEYPTR(hh, *map, tmp->r_key, strlen(tmp->r_key), tmp);
+ }
+ return ans_str;
+}
+
+struct TreeNode **findDuplicateSubtrees(struct TreeNode *root,
+ int *returnSize) {
+ struct TreeNode **ans = malloc(sizeof(struct TreeNode *) * 250);
+ *returnSize = 0;
+ h_elem *map = NULL;
+ dfs(root, &map, ans, returnSize);
+ return ans;
+}