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;
}