Twitter 店面

6月份的店面[hide=150]
判断一个二叉树是否是镜面对称， LC 上

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

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

间如何处理
[/hide=150]

楼主请问下有环的话怎么做的，不用额外空间是用dfs吗 谢谢

楼主请问下有环的话怎么做的 请加米~

liu夜尽天明 发表于 2019-11-15 15:01
楼主请问下有环的话怎么做的 请加米~

有环的话那就变成了再一个图里面搜索， 最简单的办法是把访问过的结点存起来

Gary.W 发表于 2019-11-15 15:05
有环的话那就变成了再一个图里面搜索， 最简单的办法是把访问过的结点存起来

那样的话岂不是要用额外存储，难道是有环跟不能用额外存储是不同的题目？不需要考虑环是否对称吗？

所以第二问才是如何不用额外空间判断是否有环

Gary.W 发表于 2019-11-15 15:14
所以第二问才是如何不用额外空间判断是否有环

没太明白，问题在我看来有点不well defiend，第二问如果有环，怎么定义symmetric tree呢

不不不， 其实这一问已经和最开始的问题没关系了， 他就是直接的问如何判断一个树是否合法（是否存在环）。 这个问题的逻辑非常好理解， 最开始他问的是如何判断sysmmetric tree, 写之前clarify了这个一定是个合法的树。 写完之后他问那现在这个input 不一定合法你如何处理。 这个可以用一个hash map 存访问过的结点。 然后他又继续问如果不用额外空间如何判断是否有环。 我当时说的是用一个指针做正常的in order traversal， 另一个指针做两倍速的in order traversal， 如果两指针相遇说明有环。 他跟我说了一个他的想法， 现在OS 都是32 bit 或者 64 bit， 也就是说指针地址最后一位一定是0， 他可以用指针地址的最后一位来记录这个指针是否被访问过。 不过讲道理我觉得他这个做法非常的赖皮。