snapchat 电面

给一个树的root node,返回same subtree及个数:
/*
                    10
                /        \
            8                3
          /  \   

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

)做,自下而上每个节点处得到一个关于以该节点为根的subtree的String,然后存入HashMap,最后根据HashMap判断.另外只有叶子的subtree不予考虑.

求加点大米,多谢

一个node的subtree算吗....其实这题考的就是serialise / deserialise binary tree? 至于要不要后续遍历其实无所谓吧...毕竟你所有节点开始的子树都要存一下的...

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

请问楼主，是说对每个节点preorder + inorder转成String一次么？ 这样才能确定一棵树吧？

小A要当码农 发表于 2016-11-10 11:23
请问楼主，是说对每个节点preorder + inorder转成String一次么？ 这样才能确定一棵树吧？

楼主的例子厘米有重复的node value，所以两个order转string结果不唯一，不能这样转

工图新一 发表于 2016-11-10 11:50
楼主的例子厘米有重复的node value，所以两个order转string结果不唯一，不能这样转

啥意思？ 我对于null节点用“＃”表示的话，两个order应该是可以转的吧？

小A要当码农 发表于 2016-11-10 11:59
啥意思？ 我对于null节点用“＃”表示的话，两个order应该是可以转的吧？

null用#表示的话，只用存preorder，转string，就可以了吧？

海盗包子 发表于 2016-11-10 12:19
null用#表示的话，只用存preorder，转string，就可以了吧？

对的。。我试了一下 好像可以

小A要当码农 发表于 2016-11-10 11:23
请问楼主，是说对每个节点preorder + inorder转成String一次么？ 这样才能确定一棵树吧？

只用postorder就行,但是把null node也表示出来,比如用"#"

海盗包子 发表于 2016-11-10 12:19
null用#表示的话，只用存preorder，转string，就可以了吧？

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