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=慢。