采采的生活隨筆: Uva 112 Tree Summing

2016年3月31日星期四

題目來源：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=48

題意：題目會提供一個數字n，和一個Binary Tree(二元樹)，請你算出二元樹根(root)到葉(left)的路徑經過的node值總和。

想法：

input的地方:

1) ()
2) (int()())
3) (int(int()())(int()()))

有沒有發現一個規律，
"(" + "內容物" + ")"
對吧?

所以輸入的地方可以寫成

	int x;
	char ch;

	cin>>x;
	cin>>ch;//讀"("
	cin>>x;//讀內容物
	if(!cin){
	cin.clear();//如果內容物不是int，就把剛剛讀的東西吐出來
	}
	cin>>ch; // ch=='(';

view raw int.cpp hosted with ❤ by GitHub

再把上面整段放入遞回函式。
就可以邊輸入邊計算了

程式碼：

	#include<iostream>
	using namespace std;
	struct node
	{
	int right = -1, left = -1;//記錄sub node是否為null
	int node_number = 0;//記錄節點數
	};

	int N;
	bool flag = 0;

	void input(int sum,node* n) {
	char c;
	int a;
	cin >> c;//讀'('

	cin >> a;
	//抓到')'，判斷是否為葉子
	if (!cin) {
	cin.clear();
	n->node_number++;
	if (n->node_number % 2) n->left = 0;
	else n->right = 0;
	if((n->left==0) && (n->right==0))
	if (N == sum) flag = 1;
	}

	//抓到數字
	else {
	sum += a;
	n->node_number++;
	if (n->node_number % 2) n->left = 1;
	else n->right = 1;
	node* w = new node;
	input(sum,w);
	input(sum,w);
	}

	//讀')'
	cin >> c;
	}

	int main() {

	while (cin >> N) {
	node* a = new node;
	flag = 0;
	input(0,a);
	if (flag) cout << "yes" << endl;
	else cout << "no" << endl;
	}
	}

view raw uva112.cpp hosted with ❤ by GitHub

注意：只有此網誌的成員可以留言。

2016年3月31日 星期四