2008年11月25日 星期二

UVa 112 Tree Summing

終於AC了..這次最大的心得就是,腦袋不清楚的時候不要寫程式。如果沒辦法理清思路,找出邏輯上的漏洞,那麼debug也只是亂試一通而已,一點幫助都沒有(只有浪費時間)。寫到後來連錯誤的測資也在試,現在想起來真是笨阿

我用recursive的方法去追蹤整顆樹。測資是pre-order sequence
所以遞回順序是root ,left-child , right-child

很不清楚核心Algo:
int traversal(int sum, int target){
    抓左括號
    抓root
    lc = traversal(int sum+root, int target) //向left-child遞回
    rc = traversal(int sum+root, int target) //向right-child遞回  
    抓右括號

    如果是Leaf? 判斷總和相不相等?
    如果是Internal Node,將子樹的結果繼續往上回傳。
}

另外一提,這次我參考了某份AC Code,用non-recursive(Stack)作法,但是因為用了STL stack;,最後執行時間0.510s,慢了我五倍之多。我用Recursive反而執行時間只有0.100s(Ranking 90,再進百大XDDDD)有點意外。證明一件事:Recursive不一定慢,但是STL=慢。