M25145: 猜二叉树（按层次遍历）

http://cs101.openjudge.cn/practice/25145/

思路：先根据二叉树的中序遍历和后序遍历序列构建二叉树，然后进行层次遍历

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

struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c) : val(c), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(string& inorder, int inStart, int inEnd, string& postorder, int postStart, int postEnd) {
    if (inStart > inEnd) return nullptr; 
    char rootVal = postorder[postEnd];  
    TreeNode* root = new TreeNode(rootVal);
    int rootIdx = inorder.find(rootVal, inStart); 
    int leftLen = rootIdx - inStart;          
    root->left = buildTree(inorder, inStart, rootIdx - 1, postorder, postStart, postStart + leftLen - 1);
    root->right = buildTree(inorder, rootIdx + 1, inEnd, postorder, postStart + leftLen, postEnd - 1);
    return root;
}
string levelOrder(TreeNode* root) {
    if (!root) return "";
    queue<TreeNode*> q;
    q.push(root);
    string res;
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        res += node->val;
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        string inorder, postorder;
        cin >> inorder >> postorder;
        TreeNode* root = buildTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
        cout << levelOrder(root) << endl;
    }
    return 0;
}