s**o
发帖数: 30 | 1 看似很简单的一个函数，查看一个BST有没有loop，我的代码是，没有那一行“remove
”的代码就会错，我现在还没想明白。。。。
public static boolean cycle(TreeNode root, HashSet visited) {
if (root == null) {
return true;
}
if (visited.contains(root.c)) {
return false;
}
visited.add(root.c);
boolean res = cycle(root.left, visited)&& cycle(root.right, visited);
//没有这一行就会错，为啥？？？？？？？？？？
visited.remove(root.c);
return res;
} |
D*********S
发帖数: 21 | 2 代码写的可读性太差，逻辑有点混乱
不过确实是错的，因为tree的traversal比较特别，不能删掉flag
自己走一遍，别想当然, 比如很简单的树，
而且还要看你bst loop具体是怎么定义的了 |
s********k
发帖数: 6180 | 3 经典的recursive做法吗？跟做combinition只push不pop会错一个道理
remove
{
【在 s**o 的大作中提到】
: 看似很简单的一个函数，查看一个BST有没有loop，我的代码是，没有那一行“remove
: ”的代码就会错，我现在还没想明白。。。。
: public static boolean cycle(TreeNode root, HashSet visited) {
: if (root == null) {
: return true;
: }
: if (visited.contains(root.c)) {
: return false;
: }
: visited.add(root.c);
|
j******o
发帖数: 4219 | |
S**********n
发帖数: 250 | |
w****6
发帖数: 796 | 6 boolean hasCycle(TreeNode node, Set set)
{
if (node == null)
return false;
if (!set.add(node))
return true;
else
return hasCycle(node.left, set) || hasCycle(node.right, set);
} |
Y******g
发帖数: 16 | 7 这个没法处理重复的value吧
【在 S**********n 的大作中提到】
: 赞
:
: ：你的BST里有没有重复的value?
|
d******y
发帖数: 2 | 8 如果 左子树的一个节点指向右子树的一个节点不算loop的话， 你的算法就会出差
A have 2 children B , and C
Also B point to C
Then your method will put C as visited when visiting B,
Later on when you visit C, you will get a false.
This is not a hard issue if you know the test case |
