二叉树的先序后续中序代码完整代码
时间: 2023-10-13 19:07:05 浏览: 132
二叉树先序和中序求后序
以下是二叉树的先序、中序、后序遍历的完整代码实现(C++语言):
```c++
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
TreeNode* build(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return NULL;
}
int rootVal = preorder[preStart];
int rootIndex = 0;
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 = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1);
root->right = build(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd);
return root;
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
preorder(root, res);
return res;
}
void preorder(TreeNode* root, vector<int>& res) {
if (root == NULL) {
return;
}
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
void inorder(TreeNode* root, vector<int>& res) {
if (root == NULL) {
return;
}
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
postorder(root, res);
return res;
}
void postorder(TreeNode* root, vector<int>& res) {
if (root == NULL) {
return;
}
postorder(root->left, res);
postorder(root->right, res);
res.push_back(root->val);
}
};
```
其中,`buildTree` 函数用来构建二叉树,`preorderTraversal` 函数用来进行先序遍历,`inorderTraversal` 函数用来进行中序遍历,`postorderTraversal` 函数用来进行后序遍历。
阅读全文