题目描述
按中序遍历和后序遍历给出一棵二叉树，求这棵二叉树中叶子节点权值的最小值。
输入保证叶子节点的权值各不相同。
输入
测试数据有多组 对于每组测试数据，首先输入一个整数N (1 <= N <= 10000)，代表二叉树有N个节点，接下来的一行输入这棵二叉树中序遍历的结果，最后一行输入这棵二叉树后序遍历的结果 输入一直处理到文件尾(EOF)
输出
对于每组测试数据，输出一个整数，代表二叉树中叶子节点权值最小值
输入样例1
7 3 2 1 4 5 7 6 3 1 2 5 6 7 4 8 7 8 11 3 5 16 12 18 8 3 11 7 16 18 12 5 1 255 255
输出样例1
1 3 255
思路分析
是要找出权值最小的叶子节点。
首先根据中序和后序遍历找出叶子节点。
因为叶子节点是没有左子树和右子树的节点，所以根据后序找出根节点，根据中序找出根节点的左右子树，这里使用递归，发现左右都是空的节点就是叶子节点，再用一个min变量找出最小的即可。
注意输入多组数据。
AC代码
代码语言：javascript复制#include<iostream>
using namespace std;
bool recursion(int *postorder, int *inorder, int last,int&min) {
if (last < 0)
return true;
int root = 0;
for (int i = 0; i <= last; i )
if (inorder[i] == postorder[last]) {
root = i;
break;
}
if(recursion(postorder, inorder, root - 1,min)&&recursion(postorder root, inorder root 1, last - root - 1,min)){
if(min>postorder[root])
min=postorder[root];
return true;
}
return false;
}
int main() {
int size;
while (cin >> size){
int postorder[size], inorder[size];
for (int i = 0; i < size; i )
cin >> inorder[i];
for (int i = 0; i < size; i )
cin >> postorder[i];
int min=0x3f3f3f3f;
recursion(postorder, inorder, size - 1,min);
cout<<min<<endl;
}
}
