题解 | 二叉树遍历

#include <iostream>
#include <string>
using namespace std;
struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c):data(c),left(nullptr),right(nullptr){};
};

//前序遍历和中序遍历构建二叉树
TreeNode* buildTree(string preorder,string inorder){
    if(preorder==""||inorder=="") return nullptr;
    char c = preorder[0];
    TreeNode *node=new TreeNode(c);
    int pos = inorder.find(c);
    node->left = buildTree(preorder.substr(1,pos), inorder.substr(0,pos));
    node->right = buildTree(preorder.substr(1+pos),inorder.substr(pos+1));
    return node;
}

void PrintPostOrder(TreeNode* tree){
    if(tree==nullptr) return;
    char c = tree->data;
    PrintPostOrder(tree->left);
    PrintPostOrder(tree->right);
    cout<<c;
}

int main() {
    string a,b;
    while(cin>>a>>b){
        TreeNode* tree = buildTree(a, b);
        PrintPostOrder(tree);
        cout<<endl;
    }
    return 0;
}