描述

给定一个二叉树的中序与后序遍历结果，请你根据两个序列构造符合这两个序列的二叉树。

数据范围：二叉树的节点数满足 1 \le n \le 1000 \1≤n≤1000  ，节点上的值满足 |val| \le 10^9 \∣val∣≤109 ，保证节点的值各不相同

例如输入[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]
复制
返回值： 
{1}
复制

示例2

输入： 
[2,1,4,3,5],[2,4,5,3,1]
复制
返回值： 
{1,2,3,#,#,4,5}

解题思路：
根据中序遍历和后序遍历的规则确定根节点
注意做子树的长度的计算
注意左右子树起始位置的传参计算 

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    
    TreeNode* func(vector<int>& inorder, int inBegin, int inEnd, vector<int>& postorder, int postBegin, int postEnd) {
        if (inBegin < 0 || inEnd >= inorder.size() || inBegin > inEnd) {
            return NULL;
        }
        if (postBegin < 0 || postEnd >= postorder.size() || postBegin > postEnd) {
            return NULL;
        }
        TreeNode* head = new TreeNode(postorder[postEnd]);

        int index;
        for (int i = inBegin; i <= inEnd; i++) {
            if (inorder[i] == postorder[postEnd]) {
                index = i;//根节点索引
            }
        }
        int leftsize = index - inBegin;
        head->left = func(inorder, inBegin, index-1, postorder, postBegin, postBegin+leftsize-1);
        head->right = func(inorder, index+1 ,inEnd, postorder, postBegin+leftsize, postEnd-1); 
        return head;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param inorder int整型vector 中序遍历序列
     * @param postorder int整型vector 后序遍历序列
     * @return TreeNode类
     */
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // write code here
        if (inorder.size() == 0 || postorder.size() == 0) {
            return {};
        }
        TreeNode* head = func(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);
        return head;

    }
};