一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 983|回复: 16
收起左侧

snapchat 电面

[复制链接] |试试Instant~ |关注本帖
wju 发表于 2016-11-10 10:39:11 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
给一个树的root node,返回same subtree及个数:
/*
                    10
                /        \
            8                3
          /  \            /     \
         4    5        8           5
             /       /   \        /
            3       4     5      3
                         /
                        3
      Expects:
             8
            / \
           4   5      Count: 2
              /.鏈枃鍘熷垱鑷1point3acres璁哄潧
             3

             5
            /         Count: 3
           3
    */
用递归的postorder traversal的方法+HashMap<String, Integer>()做,自下而上每个节点处得到一个关于以该节点为根的subtree的String,然后存入HashMap,最后根据HashMap判断.另外只有叶子的subtree不予考虑.

求加点大米,多谢. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

评分

2

查看全部评分

小A要当码农 发表于 2016-11-10 11:23:55 | 显示全部楼层
请问楼主,是说对每个节点preorder + inorder转成String一次么? 这样才能确定一棵树吧?
回复 支持 反对

使用道具 举报

在浙里 发表于 2016-11-10 11:32:13 | 显示全部楼层
感谢分享,感觉楼主能拿onsite
回复 支持 反对

使用道具 举报

工图新一 发表于 2016-11-10 11:50:52 | 显示全部楼层
小A要当码农 发表于 2016-11-10 11:23
请问楼主,是说对每个节点preorder + inorder转成String一次么? 这样才能确定一棵树吧?

楼主的例子厘米有重复的node value,所以两个order转string结果不唯一,不能这样转
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-10 11:59:57 | 显示全部楼层
工图新一 发表于 2016-11-10 11:50.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主的例子厘米有重复的node value,所以两个order转string结果不唯一,不能这样转

啥意思? 我对于null节点用“#”表示的话,两个order应该是可以转的吧?
回复 支持 反对

使用道具 举报

海盗包子 发表于 2016-11-10 12:19:26 | 显示全部楼层
小A要当码农 发表于 2016-11-10 11:59
啥意思? 我对于null节点用“#”表示的话,两个order应该是可以转的吧?

null用#表示的话,只用存preorder,转string,就可以了吧?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-10 12:24:28 | 显示全部楼层
海盗包子 发表于 2016-11-10 12:19
null用#表示的话,只用存preorder,转string,就可以了吧?

对的。。我试了一下 好像可以
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-11-10 13:57:13 | 显示全部楼层
一个node的subtree算吗....其实这题考的就是serialise / deserialise binary tree? 至于要不要后续遍历其实无所谓吧...毕竟你所有节点开始的子树都要存一下的...

补充内容 (2016-11-10 14:46):
想了一下还是后序遍历省时间
回复 支持 反对

使用道具 举报

 楼主| wju 发表于 2016-11-11 02:13:27 | 显示全部楼层
小A要当码农 发表于 2016-11-10 11:23
请问楼主,是说对每个节点preorder + inorder转成String一次么? 这样才能确定一棵树吧?

只用postorder就行,但是把null node也表示出来,比如用"#"
回复 支持 反对

使用道具 举报

 楼主| wju 发表于 2016-11-11 02:17:26 | 显示全部楼层
海盗包子 发表于 2016-11-10 12:19
null用#表示的话,只用存preorder,转string,就可以了吧?

为什么用preorder?用postorder自下而上每到一个节点就可以得到一个string,在这个string的基础上再往上走就可以得到上一级节点的subtree的string
回复 支持 反对

使用道具 举报

海盗包子 发表于 2016-11-11 05:27:21 | 显示全部楼层
wju 发表于 2016-11-11 02:17
为什么用preorder?用postorder自下而上每到一个节点就可以得到一个string,在这个string的基础上再往上走 ...
. 1point 3acres 璁哄潧
我觉的preorder和postorder都可以的,做法一样的吧,用recursion写,唯一区别就是root值放前还是后
回复 支持 反对

使用道具 举报

Toby 发表于 2016-11-12 10:33:24 | 显示全部楼层
求问楼主收到onsite了吗?
回复 支持 反对

使用道具 举报

Jess. 发表于 7 天前 | 显示全部楼层
求问最后的输出 map 中的 key 是需要自己重新把 string 变回 node 存进去吗? 谢谢!
回复 支持 反对

使用道具 举报

 楼主| wju 发表于 7 天前 | 显示全部楼层
Jess. 发表于 2016-12-3 03:24
求问最后的输出 map 中的 key 是需要自己重新把 string 变回 node 存进去吗? 谢谢!

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

使用道具 举报

豆虫 发表于 7 天前 | 显示全部楼层
谢谢楼主分享,感觉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});. 1point3acres.com/bbs
30         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
31         return res;
32 }
33
34 string dfs(unordered_map<string,int>& Map,TreeNode *cur){
35         if(!cur)return "#";
.1point3acres缃 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 }
回复 支持 反对

使用道具 举报

Jess. 发表于 6 天前 | 显示全部楼层
wju 发表于 2016-12-3 04:36
当时没做完,我的map里就存String,对于如何返回子树根节点,还没来得及做,你有什么方法吗

我想的是 map 存 string 和 node
回复 支持 反对

使用道具 举报

在浙里 发表于 6 天前 | 显示全部楼层
感谢分享,祝好运
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 13:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表