网易笔试求解

第一道题：二叉树字符编码找重复子树

给定一棵中序遍历的二叉树，如果当前树为空则表示为X，如果不为空则表示为(left_tree)cur_value(right_tree)，其中left_tree和right_tree分别表示按此规则序列化之后的左右子树字符串。找出重复子树的数量，相同子树只计算一次。

输入：

字符编码的二叉树

输出：

重复子树的个数

例子：

输入：

((X)2(X))1(((X)4(X))3((X)2(X)))

输出：

1

解释：只有相同节点2

这题我的做法就是中心扩展找出所有可能的子树，利用哈希表来发现重复的子树，但是不知道为什么只过了66.7，并没有提示是超时等问题，想问问大佬的解决方案。

第二题：归元等运算

定义运算规则(=)为归元等，对于字符串string1和string2分别去重之后构成的字符集合S1和S2，如果S1和S2中的元素完全相等，则string1和string2就具有归元等的关系，如aabbc233 (=) a32bcca，因为两个字符串都是由a,b,c,2和3这五个字符组成的。

现给出一个字符串A和一组字符串B[n]，问有多少种i和j的选择，可以满足等式B[i] + A (=) B[j]

输入：

第一行：字符串A

第二行：B中字符串的数量

第三行至最后一行：每行一个字符串：B1, B2, B3 ...

输出：

一共多少种组合，限制i不等于j，但是Bi可以等于Bj

这题我就疯狂哈希模拟了一波直接超时，求大佬的解决方案