题解 | 二叉树遍历

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

typedef struct btree {
    struct btree *left;
    struct btree *right;
    char c;
} btree;

// 根据前序和中序构建二叉树的递归函数
btree* build(string pre, string in) {
    if (pre.empty() || in.empty()) 
    return NULL;

    // 创建根节点（前序遍历第一个字符）
    btree* node = new btree();
    node->c = pre[0];
    node->left = node->right = NULL;

    // 在中序中找到根节点位置
    size_t root_pos = in.find(pre[0]);
    
    // 分割左右子树的中序字符串
    string left_in = in.substr(0, root_pos);
    string right_in = in.substr(root_pos + 1);

    // 分割左右子树的前序字符串
    string left_pre = pre.substr(1, left_in.length());
    string right_pre = pre.substr(1 + left_in.length());

    // 递归构建子树
    node->left = build(left_pre, left_in);
    node->right = build(right_pre, right_in);

    return node;
}

// 后序遍历输出
void postOrder(btree* t) {
    if (!t) return;
    postOrder(t->left);
    postOrder(t->right);
    cout << t->c;
}

int main() {
    
    string pre, in;
    while(cin>>pre>>in)
    {
    btree* root = build(pre, in);  // 构建二叉树
    postOrder(root);  // 输出后序
    cout<<endl;
    }

}