一个二叉树的节点分别用A,B,C,...表示。用户以前序遍历的方式输入节点字符串,如”ACDBE...“,再以中序遍历的方式输入一个字符串,要求判断两次输入的字符串能否唯一确定一棵二叉树,如果不能,输出否,如果能,则以后序遍历的方式输出这棵二叉树。要求使用c++
时间: 2024-06-13 22:08:46 浏览: 14
以下是解决该问题的C++代码,该代码使用了递归的方法,首先根据前序遍历和中序遍历构建二叉树,然后再进行后序遍历输出。
```c++
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* buildTree(string preorder, string inorder) {
if (preorder.empty() || inorder.empty()) {
return nullptr;
}
unordered_map<char, int> inorder_map;
for (int i = 0; i < inorder.size(); ++i) {
inorder_map[inorder[i]] = i;
}
return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, inorder_map);
}
TreeNode* buildTree(string& preorder, int pre_start, int pre_end, string& inorder, int in_start, int in_end, unordered_map<char, int>& inorder_map) {
if (pre_start > pre_end || in_start > in_end) {
return nullptr;
}
char root_val = preorder[pre_start];
TreeNode* root = new TreeNode(root_val);
int inorder_root_index = inorder_map[root_val];
int left_tree_size = inorder_root_index - in_start;
root->left = buildTree(preorder, pre_start + 1, pre_start + left_tree_size, inorder, in_start, inorder_root_index - 1, inorder_map);
root->right = buildTree(preorder, pre_start + left_tree_size + 1, pre_end, inorder, inorder_root_index + 1, in_end, inorder_map);
return root;
}
string postorderTraversal(TreeNode* root) {
if (root == nullptr) {
return "";
}
string left_str = postorderTraversal(root->left);
string right_str = postorderTraversal(root->right);
return left_str + right_str + root->val;
}
};
int main() {
string preorder = "ACDBEFG";
string inorder = "CBDAEFG";
Solution solution;
TreeNode* root = solution.buildTree(preorder, inorder);
string postorder = solution.postorderTraversal(root);
cout << postorder << endl;
return 0;
}
```