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

	#include<iostream>
	using namespace std;
	enum
	{
	//Types of token
	LEFT_BRACKET, RIGHT_BRACKET, NUMBER,
	//return Value
	MATCH, NOT_MATCH, EMPTY_TREE
	};
	static int num;
	int getToken()
	{
	int c = getchar();
	while (c == ' ' || c == '\n')
	c = getchar();
	num = 0;
	if (c == '(')
	return LEFT_BRACKET;
	else if (c == ')')
	return RIGHT_BRACKET;
	else if ( (c >= '0' && c <= '9') || c == '-' )
	{
	int sign = 1;
	if (c == '-')
	{
	sign = -1;
	c = getchar();
	}
	for (; c >= '0' && c <= '9'; c = getchar())
	num = num * 10 + (c - '0');
	num = num * sign;
	ungetc(c, stdin);
	return NUMBER;
	}
	return 0;
	}
	int traversal(int sum, int target)
	{
	int token;
	getToken(); //get Left Bracket '('
	token = getToken();
	if (token == RIGHT_BRACKET)
	return EMPTY_TREE;
	else //if(token = NUMBER)
	sum += num;
	int lc = traversal(sum, target); //left child
	int rc = traversal(sum, target); //right child
	getToken(); //get right bracket ')'
	if (lc == EMPTY_TREE && rc == EMPTY_TREE) //leaf
	if (sum == target)
	return MATCH;
	if (lc == MATCH || rc == MATCH) //return result upwards
	return MATCH;
	return NOT_MATCH;
	}
	int main()
	{
	int target;
	//for each test case
	while (scanf("%d", &target) == 1)
	{
	if (traversal(0, target) == MATCH) //if not ok
	printf("yes\n");
	else
	printf("no\n");
	}
	return 0;
	}

view raw 112.cpp hosted with ❤ by GitHub