y*****a
发帖数: 221 | | l*****a
发帖数: 14598 | 2 what does indegree2 mean?
thanks
【在 y*****a 的大作中提到】
: 怎么找出这个node？
| y*****a
发帖数: 221 | 3 原题是这么说的
Suppose there is a binary tree having millions of nodes and by mistake one
node has two indegree........(i.e. There becomes a cycle/loop in that tree .
..u have to find that node which is having two indegree....
Constraint is no extra memory can be used and tree representation is in
Linked list format...
【在 l*****a 的大作中提到】
: what does indegree2 mean?
: thanks
| P********l
发帖数: 452 | 4 depends how the "Linked list" is organised.
Basically, a tree does not need the "Linked list", which is the extra piece
of memory that can mark a node is visited or not.
So,
1) clear the linked list.
2) from root, do a dfs / bfs traversal. once visited, push it into the
linked list.
3) if a node is already in the list, it has two indegrees.
4) continue to push all nodes in.
The linked list is virtually the same but we know who has two indegrees. |
|
