最近Leetcode上刷到了还原二叉树相关的题目：
https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

分析

利用递归方法解决此类问题。需要利用哈希表对中序遍历下不同节点值与其下标进行映射，然后利用前序或后序对整棵二叉树进行还原。

前序还原与后序还原的区别有二：
1.前序还原的idx起始值为0，即第一个元素为根节点，后序还原的idx起始值为inorder.size()-1，即最后一个元素为根节点。
2.前序遍历先递归左子树，因为前序遍历为(DLR)，根节点后面跟的是L(左子树);
后序遍历先递归右子树，因为后序遍历为(LRD)，根节点前面是R(右子树)。

前序与中序构建二叉树

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<int,int> mp;
    int idx;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n=inorder.size();
        for(int i=0;i<n;i++)
        {
            mp[inorder[i]]=i;
        }
        idx=0;          //初始根节点下标为0
        auto T = bfs(preorder,0,n-1);
        return T;
    }
    TreeNode* bfs(vector<int>& preorder,int l,int r)
    {
        if(l>r) return NULL;
        int pos = mp[preorder[idx]];
        auto root = new TreeNode(preorder[idx++]);
        root->left = bfs(preorder,l,pos-1);     //前序遍历首先递归左子树
        root->right = bfs(preorder,pos+1,r);
        return root;
    }
};

后序与中序构建二叉树

C++ 代码

class Solution {
public:
    unordered_map<int,int> mp;
    int idx;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n=inorder.size();
        for(int i=0;i<n;i++) mp[inorder[i]]=i;
        idx=n-1;        //初始根节点下标为n-1
        auto T = bfs(postorder,0,n-1);
        return T;
    }
    TreeNode* bfs(vector<int>& postorder,int l,int r)
    {
        if(l>r) return NULL;
        int pos = mp[postorder[idx]];
        auto root = new TreeNode(postorder[idx--]);
        root->right = bfs(postorder,pos+1,r);       //后序遍历先递归右子树
        root->left = bfs(postorder,l,pos-1);
        return root;
    }
};