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

叶茂林

发布于 2023-07-30 13:55:05

2940

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

题目描述

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

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

输入

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-02-18，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树