【代码超详解】UVA 548 Tree 树（二叉树、DFS）

原题：紫书 第六章 例题 6-8
第二回手写二叉树，又磕了我若干个小时，才艰难过了样例。提交的时候历经数次 WA ，然后根据紫书的代码把 DFS 的函数改了一下，AC 。

一、题目描述
输入若干个二叉树，结束标志为 EOF 。每棵二叉树占两行，分别是中序遍历和后序遍历。根据输入，输出最小路径值所在的树叶的值。已知：一条路径的值是从二叉树的根部到叶节点（包括根与叶）的每个节点的值的和。如果有多个最小的路径值，输出树叶节点的值最小的那条路径的叶节点的值。每个节点的值都是大于 0 小于 10 000 的整数，且不会重复。每棵二叉树的节点数至少为 1 ， 至多为 10 000 。

二、算法分析与代码编写指导
已知一棵二叉树的中序遍历和后序遍历，可以构造出这棵二叉树。构造完毕后，再通过 DFS（深度优先搜索）找出答案。
首先，明确前序遍历、中序遍历、后序遍历的递归定义：

PreOrder(T) = T的根结点 + PreOrder(T的左子树) + PreOrder(T的右子树)
InOrder(T) = InOrder(T的左子树) + T的根结点 + InOrder(T的右子树)
PostOrder(T) = PostOrder(T的左子树) + PostOrder(T的右子树) + T的根结点
其中，+ 运算符可以表示字符串连接等运算。
在手工列写一棵二叉树的前序遍历、中序遍历、后序遍历时，先从根节点开始，套用上述定义列写，然后将表达式中的左子树、右子树再套用上述定义展开，一直处理到每个叶节点。

本题中，输入格式可以表示为：

中序遍历中，某个节点的左子树的每个节点的值分别为

该节点的右子树的每个节点的值分别为

后序遍历中，某个节点的左子树的每个节点的值分别为

该节点的右子树的每个节点的值分别为

该节点作为与其左子树、右子树直接相连的一个根节点（可以是整个二叉树的根），其值表示为：

我们以其中一个样例为代表进行演示：
3 2 1 4 5 7 6
3 1 2 5 6 7 4

后序遍历的最后一个值 4 位于树根，在中序遍历中找到 4 的位置，左边的 3 2 1 位于左子树，右边的 5 7 6 位于右子树。
中序遍历的列写顺序是：左子树→根→右子树；后序遍历的列写顺序是：左子树→右子树→根。因此，可以确定在后续中 3 1 2 属于左子树，5 6 7 属于右子树，树根分别是 2 和 7 。在中序遍历中找到 2 和 7 的位置，确定 2 的左叶节点为 3 ，右叶节点为 1 ；7 的左叶节点为 5 ，右叶节点为 6 。
将上述建树算法推广到一般情况：
后序遍历中的最后一个数 v[r] 为树根，由于每个节点的值都不同，因此可以在中序遍历中直接查找其唯一位置，取其下标（从 0 开始）记为 p 。确定在中序遍历和后序遍历中属于左子树的下标范围分别是 [0, p - 1] 和 [p + 1, t]，属于右子树的下标范围分别是 [0, p-1] 和 [p, t - 1] 。其中 t 为输入数据的最后一个下标。得到下标后，再仿照之前的步骤继续处理，当 p = 0 时，左子树全部展开完毕；当 p = t 时，右子树全部展开完毕。
最终建立二叉树如图：

建立二叉树以后，通过 DFS 查找值最小的路径，并在查找到值相同的路径时记录最小的叶节点的值。
我们同样以该样例演示。
从根节点 4 出发，累计的路径值为 4 ，左边连接 2 ，先处理 2 。路径值为 6 。2 左边连接 3 ，右边 连接 1，先处理左边 3 ，路径累积为 9 。3 既没有左子节点也没有右子节点，一条路径处理完毕，路径值为 9 ，叶节点为 3 。再处理 2 的右边 1 ，累计的路径值为 7 ，叶节点为 1 。然后处理 4 的右边连接的 7 ，7 有左子节点 5 和右子节点 6 ，先进入左边，累计路径值为 16 ，叶节点为 5 。再处理右边，累计路径值为 17 ，叶节点为 6 。全部路径处理完毕，答案为 1（对应路径为 4→2→1 ）。

下面开始完成代码。
主程序的大致思路是：读取→建树→处理→输出。
读取部分，用 getchar() 函数依次读取字符，读取到数字时记录节点数值，读取到空格或回车时都要保存临时记录的值。当然，也可以直接保存在数组中，不用临时变量，这会使代码执行更快。这样的代码请读者自行完成。读取到 EOF 时，退出 main 函数。
根据保存的结果建立二叉树。本程序采用指针法实现二叉树，声明一个 node 结构体，每个 node 包含该节点的值和两个 node 类型的指针，分别连接左子树和右子树。
为了防止内存泄漏，需要编写删除二叉树的函数。本例采用递归法删除，从根节点开始，依次删除左子树、右子树、节点本身。为了防止对空指针操作而出错，在函数的开头先判断，如果是空指针，直接结束函数。如果读者不理解，可以自己在草稿纸上按最后的参考代码推演删除过程。
然后写建立二叉树的代码。本例采用的建树函数返回一个 node 型指针指向建立的树根，传入的参数分别是中序遍历、后序遍历、最后的下标。先在中序遍历中查找后序遍历的最后下标的值的位置并记录，求得左子树和右子树在输入数据中的范围，然后递归调用建树函数。当不满足结束条件（最后下标 lastsubscr 等于 0 时左子树全部展开，等于原输入的最后下标时右子树全部展开）时才继续建立子树。
最后写 DFS 代码。根据上面用样例演示的算法，我们可以写出相应的代码。从根节点出发，每访问一个节点时先累加路径值，然后判定左子树或右子树是否为空，如果不为空则搜索子树。每次退回到上一节点继续搜索时，都需要用到累计到上一个节点的路径值，因此在传入的参数中加入路径值。访问完叶节点以后，要将统计的路径值减回去（重新减去该节点的值），以便统计下一条搜索路径的值。
执行完毕后，输出结果即可。
本代码留有被注释掉的测试代码。当输出的结果与预期不符而在 IDE 中查看中间变量不方便（有时候无法看到部分中间变量，比如不在循环内改变的值，map / set / vector 等容器中的值等等）时，可以在写代码的过程中额外编写输出中间结果的代码，方便找出 bug 。

AC代码：（本代码根据紫书代码优化而来，紫书代码约 60 ms ，本代码只需要约 20 ms）

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
#pragma warning(disable:4996)
struct node {
	unsigned int value; node* left, * right;
	node() :value(0), left(nullptr), right(nullptr) {}
};
unsigned int InOrder[10000], PostOrder[10000], curValue = 0, dfsResult, curPathSum, minLeafNode; 
char c; bool exitfor; node* root; unsigned long long p; const unsigned long long ullub = -1;
inline node* ConstructBinaryTree(unsigned int* inorder, unsigned int* postorder, const unsigned long long& lastsubscr) {
	node* n = new node(); unsigned int* nodeptr = find(inorder, inorder + lastsubscr + 1, postorder[lastsubscr]);
	unsigned long long nodesubscr = nodeptr - inorder, subscrOff = nodesubscr + 1, nRST = lastsubscr - nodesubscr; n->value = *nodeptr;
	if (nodesubscr != 0)n->left = ConstructBinaryTree(inorder, postorder, nodesubscr - 1);
	if (nRST != 0)n->right = ConstructBinaryTree(inorder + subscrOff, postorder + nodesubscr, lastsubscr - subscrOff);
	return n;
}
inline void RemoveBinaryTree(node* root) {
	if (root == nullptr)return;
	RemoveBinaryTree(root->left); RemoveBinaryTree(root->right); delete root;
}
inline void DFS_bTree(node* root, unsigned int& curPathSum) {
	curPathSum += root->value; unsigned char r = (root->left != nullptr) * 2 + (root->right != nullptr);
	//printf("HINTS: Current Path Sum = %u, Current Node Value = %u\n", curPathSum, root->value);
	switch (r) {
	case 3:DFS_bTree(root->left, curPathSum); DFS_bTree(root->right, curPathSum); break;
	case 2:DFS_bTree(root->left, curPathSum); break;
	case 1:DFS_bTree(root->right, curPathSum); break;
	case 0:
		if (curPathSum < dfsResult) { dfsResult = curPathSum; minLeafNode = root->value; }
		else if (curPathSum == dfsResult && root->value < minLeafNode)minLeafNode = root->value;
	}
	curPathSum -= root->value; //printf("HINTS: It has gone back to previous node, current path sum = %u\n", curPathSum);
}
int main() {
	for (;;) {
		exitfor = false; p = ullub; RemoveBinaryTree(root);
		while (exitfor == false) {
			c = getchar();
			switch (c) {
			case 48:case 49:case 50:case 51:case 52:case 53:case 54:case 55:case 56:case 57:curValue = curValue * 10 + c - 48; 
				/*printf("HINTS: Current Value = %u\n", curValue); */continue;
			case ' ':InOrder[++p] = curValue; /*printf("HINTS: Current Input Value = %u\n", curValue); */curValue = 0;  continue;
			case '\n':InOrder[++p] = curValue; /*printf("HINTS: Current Input Value = %u\n", curValue); */curValue = 0; exitfor = true; continue;
			case EOF:return 0;
			}
		}
		exitfor = false; p = ullub;
		while (exitfor == false) {
			c = getchar();
			switch (c) {
			case 48:case 49:case 50:case 51:case 52:case 53:case 54:case 55:case 56:case 57:curValue = curValue * 10 + c - 48; 
				/*printf("HINTS: Current Value = %u\n", curValue); */ continue;
			case ' ':PostOrder[++p] = curValue; /*printf("HINTS: Current Input Value = %u\n", curValue); */curValue = 0; continue;
			case '\n':PostOrder[++p] = curValue; /*printf("HINTS: Current Input Value = %u\n", curValue); */curValue = 0; exitfor = true; continue;
			case EOF:return 0;
			}
		}
		//puts("TEST");
		//for (unsigned int i = 0; i <= p; ++i)
		//	printf("%u ", InOrder[i]);
		//putchar('\n');
		//for (unsigned int i = 0; i <= p; ++i)
		//	printf("%u ", PostOrder[i]);
		//printf("\nEND TEST\n");
		root = ConstructBinaryTree(InOrder, PostOrder, p); dfsResult = 4294967295, curPathSum = 0, minLeafNode = 4294967295;
		DFS_bTree(root, curPathSum); printf("%u\n", minLeafNode); 
	}
	return 0;
}