说明

vector中数列的顺序是二叉树的某种遍历序列，根据这个条件构造出这个二叉树。
力扣 105题 ， 106题

从前序与中序遍历序列构造二叉树

思路

对于任意一颗树而言，前序遍历的形式总是：[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]，即根节点总是前序遍历中的第一个节点。
中序遍历的形式总是，[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]，即根节点总是在左右子树中间。

具体操作流程：
先在前序数列中，找到根节点（也就是第一个节点），把根节点的值保存到 rtval 变量中。
由 rtval 反查中序排列对应值的下标，从后定位出根节点在中序数列的位置。
由根节点的位置，把数列一分为左右子树，再分别递归左右子树。
注意：前序数列的下一个节点是左子树的根（先递归左，再递归右），而后序数列前一个结点时右子树的根（先递归右，再递归左）。

/*
struct TreeNode {
    int val;//节点的值
    TreeNode *left;//节点的左子树
    TreeNode *right;//节点的右子树
    TreeNode():val(0),left(NULL),right(NULL){}
    TreeNode(int x):val(x),left(NULL),right(NULL){}
    TreeNode(int x,TreeNode *left,TreeNode *right):val(x),left(left),right(right){}
};
*/
class Solution {
    int p;//先序数列的游标
    map<int, int> mp;//映射中序数列从值到下标
    public:
    TreeNode* helper(int left, int right, vector<int>& preorder, vector<int>& inorder){
        if (left > right) return NULL;//如果区间没有数就返回空
        int rtval = preorder[p];//获取根节点的值
        TreeNode* root = new TreeNode(rtval);//用该值构造一个新节点root
        int i = mp[rtval];// 根据 root 所在位置分成左右两棵子树
        p++;//下一个根
        //先左后右递归顺序不能变，因为先序遍历时，先左子树根再右子树根
        root->left = helper(left, i - 1, preorder, inorder);// 递归构造左子树，并连到当前点的左子树
        root->right = helper(i + 1, right, preorder, inorder);// 递归构造右子树，并连到当前点的右子树
        return root;//把构造的节点返回
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        p = 0;// 从前序遍历的第0个元素开始
        //把下标和值反一下，因为希望通过值可以立即知道下标是多少
        for (int i=0;i<inorder.size();i++) mp[inorder[i]] = i;
        return helper(0, (int)inorder.size() - 1, preorder, inorder);
    }
};

从中序与后序遍历序列构造二叉树

/*
struct TreeNode {
    int val;//节点的值
    TreeNode *left;//节点的左子树
    TreeNode *right;//节点的右子树
    TreeNode():val(0),left(NULL),right(NULL){}
    TreeNode(int x):val(x),left(NULL),right(NULL){}
    TreeNode(int x,TreeNode *left,TreeNode *right):val(x),left(left),right(right){}
};
*/
class Solution {
    int p;//后序数列中根的位置
    map<int, int> mp;//中序数列的值和下标的映射
    public:
    TreeNode* helper(int left, int right, vector<int>& inorder, vector<int>& postorder){
        if (left > right) return NULL;//如果区间没有数就返回空
        int rtval = postorder[p];//获取根节点的值
        TreeNode* root = new TreeNode(rtval);//用该值构造一个新节点root
        int i = mp[rtval];// 根据 root 所在位置分成左右两棵子树
        p--;// 下标减一
        //先右后左的顺序不能变，因为每次p先获得右子树的根   
        root->right = helper(i + 1, right, inorder, postorder);//生成的节点作为右子树连到父节点
        root->left = helper(left, i - 1, inorder, postorder);//生成的节点作为左子树连到父节点
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        p = (int)postorder.size() - 1;// 从后序遍历的最后一个元素开始
        for (int i=0;i<inorder.size();i++) mp[inorder[i]] = i;//把下标和值反一下，因为希望通过值可以立即知道下标是多少
        return helper(0, (int)inorder.size() - 1, inorder, postorder);
    }
};