[C++知识库] C++实现：已知先序遍历和中序遍历，求后序遍历

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> C++实现：已知先序遍历和中序遍历，求后序遍历 -> 正文阅读

[C++知识库]C++实现：已知先序遍历和中序遍历，求后序遍历

///已知先序遍历和中序遍历，求后序遍历
#include <iostream>
#include <cstring>
using namespace std;

char preorder[101], inorder[101]; //先序遍历 中序遍历

//@params: preL-先序遍历左区间
//preR-先序遍历右区间
//inL-中序遍历左区间
//intR-中序遍历右区间
void func(int preL, int preR, int inL, int inR)
{
    if (preL > preR) return ;
    char root = preorder[preL]; //树根
    int ind; //树根在中序遍历中的位置

    for (int i = inL; i <= inR; ++i) {
        if (inorder[i] == root) {
            ind = i;
            break;
        }
    }

    func(preL + 1, ind -inL + preL, inL, ind - 1); //递归左子树
    func(ind -inL + preL + 1, preR, inL + 1, inR); //递归右子树
    cout << root;
}

int main()
{
    cin >> preorder >> inorder;
    func(0, strlen(preorder) - 1, 0, strlen(inorder) - 1);
    cout << endl;
    return 0;
}