假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请画出该二叉树,并写出后序序列。数据结构代码
时间: 2024-03-17 12:39:41 浏览: 55
二叉树的先序、中序、后序排列(源代码)
二叉树的节点结构体定义如下:
```c++
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};
```
可以通过递归构建二叉树,具体实现如下:
```c++
class Solution {
public:
TreeNode* buildTree(vector<char>& preorder, vector<char>& inorder) {
return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
}
private:
TreeNode* build(vector<char>& preorder, vector<char>& inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return nullptr;
}
char rootVal = preorder[preStart];
int index = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
int leftSize = index - inStart;
TreeNode* root = new TreeNode(rootVal);
root->left = build(preorder, inorder, preStart + 1, preStart + leftSize, inStart, index - 1);
root->right = build(preorder, inorder, preStart + leftSize + 1, preEnd, index + 1, inEnd);
return root;
}
};
```
构建完成后,可以进行后序遍历,得到后序序列:
```c++
class Solution {
public:
vector<char> postorderTraversal(TreeNode* root) {
vector<char> result;
postorder(root, result);
return result;
}
private:
void postorder(TreeNode* root, vector<char>& result) {
if (root == nullptr) {
return;
}
postorder(root->left, result);
postorder(root->right, result);
result.push_back(root->val);
}
};
```
阅读全文