优秀的商城网站首页设计,编程网站ide做的比较好的,中文域名网站标识,赚钱输入一个二叉树的中序和后序遍历#xff0c;请你输出一个叶子节点#xff0c;该叶子节点到根的数值总和最小#xff0c;且这个叶子是编号最小的那个。 输入#xff1a; 您的程序将从输入文件中读取两行(直到文件结尾)。第一行是树的中序遍历值序列,第二行是树的后序遍历值序…输入一个二叉树的中序和后序遍历请你输出一个叶子节点该叶子节点到根的数值总和最小且这个叶子是编号最小的那个。 输入 您的程序将从输入文件中读取两行(直到文件结尾)。第一行是树的中序遍历值序列,第二行是树的后序遍历值序列。所有值将不同大于零且小于或等于10000.二叉树的节1N10000。 输出 对于每个树描述您应该输出最小值路径的叶节点的值。存在多路径最小的情况下您应该选择终端叶子节点上具有最小值的那条路径且输出那个最小值的终端叶子。 代码如下
#include iostream
#include sstream
using namespace std;
const int N 10010;
int post_order[N], in_order[N], lch[N], rch[N];
//zhon hou
int best_sum, best;
int n;bool read_line(int *a) {string line;if (!getline(cin, line))return false;stringstream ss(line);n 0;//注意这里不能写成int n因为后面要用到n所以不要让n变成局部变量了int x;while (ss x)a[n] x;return n 0;
}int build(int inL, int inR, int postL, int postR) {if (inL inR)return 0;int root post_order[postR];int k inL;//注意这是k inL不是k 0while (in_order[k] ! root)k;int numLeft k - inL;lch[root] build(inL, k - 1, postL, postL numLeft - 1);rch[root] build(k 1, inR, postL numLeft, postR - 1);return root;
}void dfs(int u, int sum) {sum u;if (!lch[u] !rch[u])if (sum best_sum || (sum best_sum u best)) {best u;best_sum sum;}if (lch[u])dfs(lch[u], sum);if (rch[u])dfs(rch[u], sum);
}int main() {while (read_line(in_order)) {read_line(post_order);build(0, n - 1, 0, n - 1);best_sum 999999999;dfs(post_order[n - 1], 0);cout best endl;}return 0;
}
