18724 二叉树的遍历运算

### 思路

1. **递归构建树**：
   - 先序遍历的第一个节点是根节点。
   - 在中序遍历中找到根节点的位置，左边部分是左子树，右边部分是右子树。
   - 递归构建左子树和右子树。

2. **递归生成后序遍历**：
   - 递归生成左子树的后序遍历。
   - 递归生成右子树的后序遍历。
   - 根节点放在最后。

### 伪代码

```
function buildTree(preorder, inorder):
    if preorder is empty:
        return null
    root = new TreeNode(preorder[0])
    rootIndex = find root in inorder
    root.left = buildTree(preorder[1:rootIndex+1], inorder[0:rootIndex])
    root.right = buildTree(preorder[rootIndex+1:], inorder[rootIndex+1:])
    return root

function postorderTraversal(root):
    if root is null:
        return ""
    left = postorderTraversal(root.left)
    right = postorderTraversal(root.right)
    return left + right + root.value

preorder = input()
inorder = input()
root = buildTree(preorder, inorder)
postorder = postorderTraversal(root)
print(postorder)
```

### C++代码

#include <iostream>
#include <string>using namespace std;struct TreeNode {char val;TreeNode* left;TreeNode* right;TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};int findIndex(const string& str, char value, int start, int end) {for (int i = start; i <= end; ++i) {if (str[i] == value) {return i;}}return -1;
}TreeNode* buildTree(const string& preorder, int preStart, int preEnd, const string& inorder, int inStart, int inEnd) {if (preStart > preEnd || inStart > inEnd) return NULL;char rootVal = preorder[preStart];TreeNode* root = new TreeNode(rootVal);int inRoot = findIndex(inorder, rootVal, inStart, inEnd);int numsLeft = inRoot - inStart;root->left = buildTree(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1);root->right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inorder, inRoot + 1, inEnd);return root;
}void postorderTraversal(TreeNode* root, string& postorder) {if (root == NULL) return;postorderTraversal(root->left, postorder);postorderTraversal(root->right, postorder);postorder += root->val;
}int main() {string preorder, inorder;cin >> preorder >> inorder;TreeNode* root = buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);string postorder;postorderTraversal(root, postorder);cout << postorder << endl;return 0;
}