题解 | #从中序与后序遍历序列构造二叉树#

/**
 * 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
struct TreeNode* p;
int index = 0;
if(inorderLen == 0){return NULL;}
while(inorder[index]!=postorder[inorderLen-1]){
    //最后一个
    index++;
    // 如果给的正确不会出现找不到的情况
}
p = malloc(sizeof(struct TreeNode));
p->val = inorder[index];
p->left = buildTree(inorder, index, postorder, postorderLen);
// 因为长度一致，中序= x个左子树 + root+y个右子树  ，后序= x个左子树 + y个右子树 + root；
// 所以找postorder [index -1]
p->right = buildTree(inorder+index+1, inorderLen -index-1, postorder+index, postorderLen-index-1) ;
return p;
}