根据前序遍历与中序遍历 求出后序遍历(C++)

题意大概是以字符串的形式输入前序遍历和中序遍历,输出后序遍历。
一个栗子 ↓
输入:ABDEC DBEAC
输出:DEBCA

#include <iostream>
#include <string.h>
using namespace std;

void findPostorder(string preorder, int low_1, int high_1, string inorder, int low_2, int high_2, char* postorder, int low_3, int high_3) {   
    if (low_1 == high_1) {
        postorder[high_3] = preorder[low_1];
        return; 
    }
    int i;
    for (i = low_2; i <= high_2; i++) {
        if (preorder[low_1] == inorder[i]) {
            break;
        }
    }
    postorder[high_3] = preorder[low_1]; 
    findPostorder(preorder, low_1 + 1, low_1 + i, inorder, low_2, low_2 + i - 1, postorder, low_3, low_3 + i - 1);
    findPostorder(preorder, low_1 + i + 1, high_1, inorder, low_2 + i + 1, high_2, postorder, low_3 + i, high_3 - 1);
}

int main() {
    string preorder, inorder;
    cin >> preorder >> inorder;
    int length = preorder.size();
    char postorder[length];
    //对后序遍历所在的字符串数组进行填充
    findPostorder(preorder, 0, length - 1, inorder, 0, length - 1, postorder, 0, length - 1);
    for (int i = 0; i < length; i++) {
        cout << postorder[i];
    }
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 第5章 引用类型(返回首页) 本章内容 使用对象 创建并操作数组 理解基本的JavaScript类型 使用基本类型...
    大学一百阅读 3,829评论 0赞 4
  • 第2章 基本语法 2.1 概述 基本句法和变量 语句 JavaScript程序的执行单位为行(line),也就是一...
    悟名先生阅读 4,713评论 0赞 13
  • 官网 中文版本 好的网站 Content-type: text/htmlBASH Section: User ...
    不排版阅读 4,910评论 0赞 5
  • 数组在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称...
    朱森阅读 4,382评论 2赞 13
  • 数据存储的核心都是写文件。 在iOS开发过程中,不管是做什么应用,都会碰到数据保存的问题。将数据保存到本地,能够让...
    ZoeZhouZ阅读 1,663评论 0赞 1

友情链接更多精彩内容