我在嘗試解Codility上面 Eta 2011的問題
http://codility.com/train/
題目的大意是這樣，給定一個m個頂點的unrooted binary tree，m為偶數。
（原題是說圖上有兩種節點，一種節點degree為3，另一種節點degree為1，
而且邊數只有 m - 1，所以應該就是unrooted binary tree）
然後給一個從樹上一點出發的in-order traversal order。
令所有leaves在此order出現的順序為 l1, l2, ..., lk, k為leaf的個數。
接著在樹上增加k條邊，分別是 (l1, l2), (l2, l3), ..., (lk-1, lk), (lk, l1)
（原題是給你一個tour，每條邊都被visit兩次，degree為1的點被visit一次，
degree為3的點被visit 3次，依照degree為1的點被visit的順序，建立一個cycle去
連接這些degree為1的點）
問在此圖上有多少條Hamiltonian Circuit。
雖然我可以知道這個圖是3-regular，同時也是planar，但是好像對於找出
Hamiltonian Circuit的數量沒有太大幫助。
而且題目的時間複雜度要求為線性，所以複雜度高的圖論演算法或是Heuristic搜尋
都不可能是解答。
我是不是漏了什麼重要線索？