uva 548

给出一棵树的中序与后序遍历结果，其中每个节点的值不重复，求根节点到叶子节点的最短权和（路径上所有节点的权相加）对应的叶子节点。如果存在多个，则输出叶子权值最小的那个。

• 后序遍历：左子树后序遍历-右子树后序遍历-树的根节点，直接得到根节点
• 中序遍历：左子树中序遍历-根节点-右子树中序遍历，在掌握根节点的位置和树的中序遍历结果时，可以求出左右子树的节点数
• 同时利用notleaf做标记：已经判断有子树的，标true。这个数组的首尾封住，可以避免单独判断出界问题
• 遍历一个树的步骤：
  1. 给出其后序遍历，得到根节点
  2. 在中序遍历中得到左右子树的节点数，就可以确定左右子树的后序遍历，形成递归

#include <iostream>
#include <cstring>using namespace std;#define MAXSIZE 10000bool notleaf[MAXSIZE + 2];
int inoder[MAXSIZE], postorder[MAXSIZE];int cnt;
int smallest, with;int whichRoot(int k)
{int ret = 0;for (; inoder[ret] != k; ++ret);return ret;
}
int left_cnt(int cur)
{int ret = 0;while (!notleaf[cur--])++ret;return ret;
}void explore(int total, int b, int e)
{//这个子树不存在if (b > e)return;int root = postorder[e];total += root;//叶子节点if (b == e){if (smallest >= total){smallest = total;with = min(smallest, root);}return;}int pos = whichRoot(root);notleaf[pos + 1] = true; //至少存在一个子树int lcnt = left_cnt(pos);explore(total, b, b + lcnt - 1); //左子树explore(total, b + lcnt, e - 1); //右子树
}int main()
{while (1){cnt = 0;smallest = MAXSIZE * MAXSIZE;with = MAXSIZE;while (1)	//输入{if (!(cin >> inoder[cnt++]))return 0;if (getchar() == '\n')break;}for (int i = 0; i != cnt; ++i)cin >> postorder[i];memset(notleaf, 0, (cnt + 2) * sizeof(bool));notleaf[0] = notleaf[cnt + 1] = true;explore(0, 0, cnt - 1);cout << with << '\n';}return 0;
}