本篇同步發布於Blog: [解題] UVa - 548 Tree

平台：

UVa Online Judge

題號：

548 - Tree

題目連結：

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=489

題目說明：

給一個樹的中序(Inorder)和後序(Postorder)，求這個樹的葉子到根的值總和是最小的路徑，並輸出那路徑的葉子值。假如有多個路徑的總和最小值相同，則輸出葉子值是最小的。

樹的節點最多會有10000個、最少1個。

範例輸入：

3 2 1 4 5 7 6

3 1 2 5 6 7 4

7 8 11 3 5 16 12 18

8 3 11 7 16 18 12 5

255

255

範例輸出：

1

3

255

解題方法：

經典的樹狀資料結構問題，首先要將後序與中序的關係釐清，並建立原來的樹，即可用深度搜尋去找路徑。

以下用畫圖解釋第1個範例輸入，原始的中序與後序如圖1

圖1

目前後序的最右邊值，為目前的根，也就是4，對應到中序，可區分左子樹與右子樹的範圍，如圖2。接著我們往左子樹遞迴找子節點。

圖2

4節點的左子樹範圍，2的後序索引值是最大的，所以2是連著4的節點，在中序又可區分左子樹與右子樹的範圍，如圖3。

圖3

2的左子樹與右子樹再遞迴處理後是3和1，如圖4與圖5。

圖4

圖5

4節點的右子樹範圍，7的後序索引值是最大的，所以7是連著4的節點，在中序又可區分左子樹與右子樹的範圍，如圖6。

圖6

7的左子樹與右子樹再遞迴處理後是5和6，如圖7與圖8。

圖7

圖8

最終答案是(4 + 2 + 1)的路徑總和是最小的 ,於是輸出這路徑的節點1。

而程式碼使用遞迴的方式解析中序和後序，再用Linked List建立樹。

難度為Medium

程式碼：

#include <iostream>
#include <string>
#include <sstream>
#include <map>
using namespace std;

map<int, int> inorderMapIndex;
int postorderNodes[10005];
int inorderNodes[10005];
int ans;
int ans_sums;

struct TreeNode{
	TreeNode* left;
	TreeNode* right;
	int val;
	TreeNode(){};

	TreeNode(int initVal)
	{
		val = initVal;
		left = NULL;
		right = NULL;
	}
};

TreeNode* parseNodes(int L1, int R1, int L2, int R2){
	if(L1 > R1){
		return NULL;
	}
	
	int inorderIndex = inorderMapIndex[postorderNodes[R2]];
	int leftCounts = inorderIndex - L1;
	TreeNode* curParent = new TreeNode(postorderNodes[R2]);
	curParent->left = parseNodes(L1, inorderIndex-1, L2, L2 + leftCounts - 1);
	curParent->right = parseNodes(inorderIndex + 1, R1, L2 + leftCounts, R2 - 1);
	
	return curParent;
}

void findLeastVal(TreeNode* node, int sum){
	if(node == NULL)
		return;
	
	sum += node->val;
	
	findLeastVal(node->left, sum);
	findLeastVal(node->right, sum);
	
	if(node->left == NULL && node->right == NULL){
		if(sum < ans_sums || (sum == ans_sums && ans > node->val)){
			ans = node->val;
			ans_sums = sum;
		}
	}
	

}


int main() 
{
    string s;
	while(getline(cin, s)){
		inorderMapIndex.clear();
		int curVal;
		int totalLength = 0;
		
		stringstream ss1(s);
		while(ss1 >> curVal){
			inorderMapIndex[curVal] = totalLength;
			inorderNodes[totalLength] = curVal;
			totalLength++;
		}
		
		totalLength = 0;
		getline(cin, s);
		stringstream ss2(s);
		while(ss2 >> curVal){
			postorderNodes[totalLength] = curVal;
			totalLength++;
		}
		
		TreeNode* root = parseNodes(0, totalLength-1, 0, totalLength-1);
		
		ans_sums = 999999999;
		findLeastVal(root, 0);
		
		cout << ans << endl;
	}


    return 0;
}

GITHUB位置：

https://github.com/u8989332/ProblemSolving/blob/master/UVaOnlineJudge/500-599/548.cpp