snapchat 电面

wju 发表于 2016-11-11 02:17
为什么用preorder?用postorder自下而上每到一个节点就可以得到一个string,在这个string的基础上再往上走 ...

我觉的preorder和postorder都可以的，做法一样的吧，用recursion写，唯一区别就是root值放前还是后

求问楼主收到onsite了吗？

求问最后的输出 map 中的 key 是需要自己重新把 string 变回 node 存进去吗？ 谢谢！

Jess. 发表于 2016-12-3 03:24
求问最后的输出 map 中的 key 是需要自己重新把 string 变回 node 存进去吗？ 谢谢！

当时没做完，我的map里就存String，对于如何返回子树根节点，还没来得及做，你有什么方法吗

谢谢楼主分享，感觉dfs+HashMap 可以做

补充内容 (2016-12-3 10:58):
21 vector<pair<int,string> > CountSameTree(TreeNode *root){
22         unordered_map<string,int> Map;
23         vector<pair<int,string> > res;
24         dfs(Map,root);
25         for(auto it=Map.begin();it!=Map.end();it++){
26                 int SharpNum=0;
27                 for(char ch : it->first)if(ch=='#')SharpNum++;
28                 if(SharpNum==2)continue;   //single node leave
29                 if(it->second>1)res.push_back({it->second,it->first});
30         }
31         return res;
32 }
33
34 string dfs(unordered_map<string,int>& Map,TreeNode *cur){
35         if(!cur)return "#";
36         string res=to_string(cur->val)+"L:";
37         res+=dfs(Map,cur->left);
38         res+="R:";
39         res+=dfs(Map,cur->right);
40         Map[res]++;
41         return res;
42 }

wju 发表于 2016-12-3 04:36
当时没做完，我的map里就存String，对于如何返回子树根节点，还没来得及做，你有什么方法吗

我想的是 map 存 string 和 node

幻灭天神 发表于 2016-12-19 08:55
用java写了下，求问Tree类的题目如何写test case比较快？

是不是可以单写一个TreeNode constructor 函数带三个value， 一个是自己的，另外两个是左右子树的