请用c语言写代码:给定一棵二叉树的前序遍历和中序遍历的结果,求其后序遍历
时间: 2024-06-06 11:10:36 浏览: 16
#include<stdio.h>
#include<stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
if(preorderSize == 0 || inorderSize == 0) return NULL;//递归终止条件
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));//新建根节点
root->val = preorder[0];
int i;
for(i = 0; i < inorderSize; i++) {//寻找根节点在中序遍历中的位置
if(inorder[i] == preorder[0]) {
break;
}
}
root->left = buildTree(preorder + 1, i, inorder, i);//建立左子树
root->right = buildTree(preorder + i + 1, preorderSize - i - 1, inorder + i + 1, inorderSize - i - 1);//建立右子树
return root;
}
void postorderTraversal(struct TreeNode* root) {//后序遍历
if(root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
int main() {
int preorder[6] = {1, 2, 4, 5, 3, 6};
int inorder[6] = {4, 2, 5, 1, 3, 6};
struct TreeNode* root = buildTree(preorder, 6, inorder, 6);
postorderTraversal(root);
return 0;
}