find treenode with two indegrees# JobHunting - 待字闺中
k*t
1 楼
看到一个题和一个答案。不太理解。
1.What does it mean that "tree representation is in Linked list format"?
Is there a standard way to represent a tree with a linked list? Or does it
just refer to the fact that TreeNode has left and right child link/pointers.
2. "When we thread a binary tree while doing preorder traversal, it wont
result in any cycle."
Is there a standard way to "thread' a binary tree? There is no "cycle"
concept at all in normal tree traversal, isn't it?
=======================================
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...
for example..
............0
........../..\
.........1...2
......../.\./.\
.......3...4...5
....../.\...\
.....6...7...8
node 4 is having two indegree....we have to find that node....
===============================================================
When we thread a binary tree while doing preorder traversal, it wont result
in any cycle. But it leads to a cycle in this case. We can make use of this
fact.
preorder:
i) Print node.
ii) If node->left is not NULL search right most node in the left subtree of
the current node and make the current nodes right child as the right child
of the found node.
iii) If node->left is NULL, go to the right subtree, ie current node=
current node->right.
This will yield a acyclic directed graph in an ideal case, but a cyclic
graph in case the indegree of any node is > 1.
1.What does it mean that "tree representation is in Linked list format"?
Is there a standard way to represent a tree with a linked list? Or does it
just refer to the fact that TreeNode has left and right child link/pointers.
2. "When we thread a binary tree while doing preorder traversal, it wont
result in any cycle."
Is there a standard way to "thread' a binary tree? There is no "cycle"
concept at all in normal tree traversal, isn't it?
=======================================
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...
for example..
............0
........../..\
.........1...2
......../.\./.\
.......3...4...5
....../.\...\
.....6...7...8
node 4 is having two indegree....we have to find that node....
===============================================================
When we thread a binary tree while doing preorder traversal, it wont result
in any cycle. But it leads to a cycle in this case. We can make use of this
fact.
preorder:
i) Print node.
ii) If node->left is not NULL search right most node in the left subtree of
the current node and make the current nodes right child as the right child
of the found node.
iii) If node->left is NULL, go to the right subtree, ie current node=
current node->right.
This will yield a acyclic directed graph in an ideal case, but a cyclic
graph in case the indegree of any node is > 1.