508.出现次数最多的子树元素和
感觉思路没问题，但编程老是报错（数组问题）。感觉数组问题是最难找错的，各种意想不到的错，太让人伤心了。
看的头大是因为一开始完全看不懂哈希，用结构体定义一个哈希节点，半猜半想能把思路理清楚，但代码还是有些难度。
这是我碰到的又一十分恶心的题，主要是有些细节不注意，又花我一整天去想哪里的bug，而且我的代码和标答高度一致都AC不了。
一个大问题是主函数中的maxcnt和cnt必须取其地址做为参数，dfs才能对齐修改，否则，dfs修改的是自己定义的形参，而不是实参。而且我试着把这2个参数用作全局变量，但还是有部分样例过不了。我实在不懂了。。。
#define MAX(a, b) ((a) > (b) ? (a) : (b))
typedef struct {
int key;
int val;
UT_hash_handle hh;
} HashItem;
int dfs(struct TreeNode *node, HashItem **cnt, int *maxCnt) {
if (node == NULL) {
return 0;
}
int sum = node->val + dfs(node->left, cnt, maxCnt) + dfs(node->right, cnt, maxCnt);
HashItem *pEntry = NULL;
HASH_FIND_INT(*cnt, &sum, pEntry);
if (NULL == pEntry) {
pEntry = (HashItem *)malloc(sizeof(HashItem));
分配空间这一步容易忘。
pEntry->key = sum;
pEntry->val = 1;
HASH_ADD_INT(*cnt, key, pEntry);
} else {
pEntry->val++;
}
*maxCnt = MAX(*maxCnt, pEntry->val);
return sum;
}
int* findFrequentTreeSum(struct TreeNode* root, int* returnSize) {
HashItem * cnt = NULL;
int maxCnt = 0;
dfs(root, &cnt, &maxCnt);
unsigned int n = HASH_COUNT(cnt);
int *ans = (int *)malloc(sizeof(int) * n);
int pos = 0;
for (HashItem *pEntry = cnt; pEntry; pEntry = pEntry->hh.next) {
if (pEntry->val == maxCnt) {
ans[pos++] = pEntry->key;
}
}
HashItem *curr, *tmp;
HASH_ITER(hh, cnt, curr, tmp) {
HASH_DEL(cnt, curr);
free(curr);
}
*returnSize = pos;
return ans;
}
572.另一颗树的子树
原来简单题对我来说就是答案理解简单而已么？代码照样想不出来。。。又是用的2个函数，每个函数里面都有递归。
Issametree判断2个树是否相同，issubtree的最后一步同时用了3个递归。很精妙。只有中间那个递归是真正判断是否有true，第1，3个递归是为了遍历所有结点，并让第二个递归返回答案。这个想法真的绝了。
这题也很容易读错，如果子树里有相同构造也不行，这里的子树是要包含本树的叶子结点的，不是从子树里再抠出一个结构来和subroot比较。
bool issametree(struct TreeNode*root,struct TreeNode*subroot){
if(root==NULL&&subroot==NULL)
return true;
else if(root==NULL||subroot==NULL)
return false;
else if(root->val==subroot->val)
return issametree(root->left,subroot->left)&&issametree(root->right,subroot->right);
return false;
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root==NULL)
return false;
if(subRoot==NULL)
return true;
return isSubtree(root->left,subRoot)||issametree(root,subRoot)||isSubtree(root->right,subRoot);
}