给定一个二叉树的中序与后序遍历结果,请你根据两个序列构造符合这两个序列的二叉树。
数据范围:二叉树的节点数满足 ,节点上的值满足 ,保证节点的值各不相同
例如输入[2,1,4,3,5],[2,4,5,3,1]时,
根据中序遍历的结果[2,1,4,3,5]和后序遍历的结果[2,4,5,3,1]可构造出二叉树{1,2,3,#,#,4,5},如下图所示:
[1],[1]
{1}
[2,1,4,3,5],[2,4,5,3,1]
{1,2,3,#,#,4,5}
#include <stdio.h> #include <string.h> #include <stdlib.h> struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param inorder int整型一维数组 中序遍历序列 * @param inorderLen int inorder数组长度 * @param postorder int整型一维数组 后序遍历序列 * @param postorderLen int postorder数组长度 * @return TreeNode类 */ struct TreeNode* buildTree(int* inorder, int inorderLen, int* postorder, int postorderLen ) { // write code here if (inorderLen < 1 || postorderLen < 1)return NULL; struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); root->val = postorder[postorderLen - 1]; int* p = inorder; for (; p < inorder + inorderLen; p++) { if (*p == postorder[postorderLen - 1]) break; } int k = p - inorder; //左子树结点数量 //递归构建左子树:中序开始位置inorder,后序开始位置postorder root->left = buildTree(inorder, k, postorder, k); //右子树结点数量inorderLen - k - 1 //递归构建右子树:中序开始位置p+1,后序开始位置postorder+k root->right = buildTree(p + 1, inorderLen - k - 1, postorder + k, inorderLen - k - 1); return root; } //前序遍历 void preOrder(struct TreeNode* root) { if (root) { printf("%d ", root->val); preOrder(root->left); preOrder(root->right); } } int main(int argc, char *argv[]) { int inorder[] = {2, 1, 4, 3, 5}; int postorder[] = {2, 4, 5, 3, 1}; int n = sizeof(inorder) / sizeof(int); struct TreeNode* root = buildTree(inorder, n, postorder, n); preOrder(root); printf("\n"); return 0; }
typedef struct TreeNode TreeNode; TreeNode* tree(int* inorder, int inL,int inR, int* postorder, int postL,int postR); struct TreeNode* buildTree(int* inorder, int inorderLen, int* postorder, int postorderLen ) { // write code here return tree(inorder,0,inorderLen-1,postorder,0,postorderLen-1); } //递归法构造 TreeNode* tree(int* inorder, int inL,int inR, int* postorder, int postL,int postR) { if(postL>postR) return NULL; TreeNode* node = malloc(sizeof(TreeNode)); node->val=postorder[postR]; int pos = inL; while(pos<=inR && inorder[pos]!=node->val) { ++pos; } node->left = tree(inorder, inL, pos-1, postorder, postL, postL+pos-inL-1); node->right = tree(inorder, pos+1, inR, postorder, postL+pos-inL, postR-1); return node; }