16年1月Snapchat电面

hakusama1024 发表于 2016-1-18 20:58
住楼主好运。请问能讲详细点不。输入的边是怎么构建树的。谢啦。

比如（A，B）表示A是B的父节点

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

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

chm34 发表于 2016-1-16 12:58
请问如何只根据（x,y）来判断y是x的左子树还是右子树呢

可以跟面试官确定，不过他说如果先出现(x,y)再出现(x,z)，就规定y是左结点z是右结点

lrn0304 发表于 2016-1-16 11:01
所以楼主是先建树, 判断合法之后再打印的么

是的呀，不过打印的时候发现不合法终止打印也可以，要求比较低。当然如果能牛到不建树直接on the fly打印也可以，不过听起来不太现实

Kidsplay 发表于 2016-1-19 13:38
是的呀，不过打印的时候发现不合法终止打印也可以，要求比较低。当然如果能牛到不建树直接on the fly打印 ...

请问楼主建树的思路是怎样  感觉挺难啊

有没有有思路如何判断有环？ 难道要node有一个father属性一路回溯看有没有一样的？

syftalent 发表于 2016-2-9 14:51
有没有有思路如何判断有环？ 难道要node有一个father属性一路回溯看有没有一样的？

判断有环方法很多的。。

我现在已经记不太清了，比如你可以用表。对于这道题其实可以更简单，打印的时候发现点超了就可以认为是有环了

这个题其实就是leetcode graph valid tree的变形，要求更严了必须是二叉树，也就是1.任何一个node的max outdegree is 2, indegree is 0 or 1, and only 1 node has 0 indegree.

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

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