在二叉樹中查找交叉鏈接

Question

在二叉樹中查找交叉鏈接的最有效方法是什麼？

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

現在這棵樹考慮4和5之間的鏈接，以便我們怎麼能發現有4交叉鏈接（即找到節點從中交聯發出）

（我在接受採訪時被問到這個問題，btw）

Answer 1

做一個BFS（http://en.wikipedia.org/wiki/Breadth-first_search）並標記訪問過的節點。

如果您曾經訪問過一個已經標記爲已訪問過的節點，那麼您將擁有一個交叉鏈接，並且交叉鏈接發出的節點就是您正在探索的子節點。