我在尝试解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搜寻
都不可能是解答。
我是不是漏了什么重要线索？