UVa 548 Tree

解題策略

典型的Binary Tree的題目，牽涉到兩個跟Binary Tree相關的動作

1. 我們知道只要有 inorder + postorder 就可得唯一的一棵 binary tree。那該怎麼把樹建起來呢 ? 我寫在 build_tree()裡。
2. 樹建起來之後，該怎麼走這顆樹，才能找出最小路徑呢? 這我寫在 do_summing( ) 函數，遞迴往下累加總和，再回傳最小的樹葉回來。

Tree 天生就是遞迴結構，用遞迴來寫再自然不過了。

注意

Tree原本應該是NULL的地方，我都掛了外部點(External Node)，這樣會讓程式碼清爽一些。

	/**
	* UVa 548 Tree (AC)
	* Author: chchwy (a) gmail.com
	* Last modified: 2010.04.22
	*/
	#include<iostream>
	#include<sstream>
	#include<vector>
	using namespace std;
	class node
	{
	public:
	int value; //the value of this node
	int sum; //the sum of path from root to current node
	node* lc, *rc;
	node()
	{
	value = 0, sum = 0;
	}
	node(int v, int s)
	{
	value = v, sum = s;
	};
	};
	node* External = new node(0, INT_MAX);
	//parse strings to a integer vector
	void parseIntLine(vector<int>& list, string& line)
	{
	stringstream sin(line);
	int n;
	while (sin >> n)
	list.push_back(n);
	}
	/* build a tree by inorder and postorder sequence */
	node* buildTree( vector<int>::iterator begin,
	vector<int>::iterator end,
	vector<int>& postorder)
	{
	if (postorder.empty())
	return External;
	vector<int>::iterator it = find(begin, end, postorder.back());
	if ( it == end ) //not found
	return External;
	int value = postorder.back(); postorder.pop_back();
	node* root = new node();
	root->value = value;
	root->rc = buildTree(it + 1, end, postorder);
	root->lc = buildTree(begin, it, postorder);
	return root;
	}
	node* do_summing(node* cur, int path_sum)
	{
	if (cur == External) return External;
	//往下累加path sum
	cur->sum = cur->value + path_sum;
	node* lc = do_summing(cur->lc, cur->sum);
	node* rc = do_summing(cur->rc, cur->sum);
	if (lc == External && rc == External) //leaf node
	return cur;
	//回傳最小的leaf node
	return (lc->sum < rc->sum) ? lc : rc;
	}
	int main()
	{
	#ifndef ONLINE_JUDGE
	freopen("548.in", "r", stdin);
	#endif
	string line1, line2;
	while ( getline(cin, line1) && getline(cin, line2) )
	{
	vector<int> inorder, postorder;
	parseIntLine(inorder, line1);
	parseIntLine(postorder, line2);
	node* root = buildTree(inorder.begin(), inorder.end(), postorder);
	printf("%d\n", dfs(root, 0)->value );
	}
	return 0;
	}

view raw 548.cpp hosted with ❤ by GitHub