中后序遍历构建二叉树与应用I

目录

题目描述

思路分析

AC代码

---

题目描述

按中序遍历和后序遍历给出一棵二叉树，求这棵二叉树中叶子节点权值的最小值。

输入保证叶子节点的权值各不相同。

输入

测试数据有多组
对于每组测试数据，首先输入一个整数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代码

#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;}
}