在二叉树中查找交叉链接

Question

在二叉树中查找交叉链接的最有效方法是什么？

 5 
    / \ 
    3 7 
    /\ /\ 
    2 4 6 8 

现在这棵树考虑4和5之间的链接，以便我们怎么能发现有4交叉链接（即找到节点从中交联发出）

（我在接受采访时被问到这个问题，btw）

Answer 1

做一个BFS（http://en.wikipedia.org/wiki/Breadth-first_search）并标记访问过的节点。

如果您曾经访问过一个已经标记为已访问过的节点，那么您将拥有一个交叉链接，并且交叉链接发出的节点就是您正在探索的子节点。