请帮我使用class用c++语言编写一段从中序和后序遍历构造二叉树并用前序遍历输出的完整代码
时间: 2023-06-24 19:09:24 浏览: 47
以下是使用class用C++语言编写一段从中序和后序遍历构造二叉树并用前序遍历输出的完整代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.empty() || postorder.empty()) {
return nullptr;
}
return buildTreeHelper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
private:
TreeNode* buildTreeHelper(vector<int>& inorder, int inStart, int inEnd, vector<int>& postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) {
return nullptr;
}
int rootVal = postorder[postEnd];
int rootIndex = -1;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
TreeNode* root = new TreeNode(rootVal);
root->left = buildTreeHelper(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSize - 1);
root->right = buildTreeHelper(inorder, rootIndex + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);
return root;
}
};
void preOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
int main() {
vector<int> inorder = {9, 3, 15, 20, 7};
vector<int> postorder = {9, 15, 7, 20, 3};
Solution s;
TreeNode* root = s.buildTree(inorder, postorder);
preOrder(root);
return 0;
}
```
在上面的代码中,我们首先定义了一个 `TreeNode` 类,表示二叉树的节点。然后定义了一个 `Solution` 类,其中包含了一个 `buildTree` 函数,该函数接受一个中序遍历序列和一个后序遍历序列,并返回由这两个序列构造的二叉树的根节点。
在 `buildTree` 函数中,我们首先判断传入的两个序列是否为空,如果有一个为空,则直接返回 `nullptr`,表示构造的二叉树为空。接着调用 `buildTreeHelper` 函数进行递归构造二叉树。`buildTreeHelper` 函数的参数分别为中序遍历序列、中序遍历序列的起始位置和结束位置、后序遍历序列、后序遍历序列的起始位置和结束位置。函数首先判断传入的起始和结束位置是否合法,如果不合法则返回 `nullptr`。然后在后序遍历序列中找到根节点的值,以此来区分左子树和右子树。然后在中序遍历序列中找到根节点的位置,以此计算出左子树的大小。接着递归构造左子树和右子树,并将它们分别赋给根节点的左右子节点。最后返回根节点。
在 `main` 函数中,我们构造了一个中序遍历序列和一个后序遍历序列,并调用 `buildTree` 函数构造二叉树。然后调用 `preOrder` 函数,用前序遍历的方式输出二叉树的所有节点值。