总结前序、中序、后序两两重建二叉树

1. 已知前序和中序遍历能重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回二叉树的后序遍历Postorder = [15, 7, 9, 20, 3]

限制：

0 <= 节点个数 <= 5000

递归

本题直接利用的是二叉树先序遍历和中序遍历的特点，通过递归来求解出答案。
1、通过前序遍历，拿到第一个节点，即为二叉树根节点；
2、利用该根节点，算出左子树节点数量，右子树节点数量；
3、利用数量和根节点在中序节点中遍历，分别算出当前二叉树左右子树的对应先序遍历列表和中序遍历列表；
4、递归求解；

/**
 * 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 {
private:
    map<int, int> dis;      //巧妙借助了map，提高检索性能，缩短时间
public:
    void PostorderTraversal(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size(); i++){
            dis[inorder[i]] = i;
        }						 //第一步存map，优化检索
        TreeNode* root = dfs(preorder, 0, preorder.size(), inorder, 0, inorder.size());					//第二步递归重建二叉树(关键！)
        Postorder(root);		 //第三步递归后序遍历二叉树
    }

    TreeNode* dfs(vector<int>& preorder, int preBegin, int preEnd, vector<int>& inorder, int inBegin, int inEnd){
        if(preBegin >= preEnd || inBegin >= inEnd){
            return nullptr;
        }
        TreeNode* root = new TreeNode(preorder[preBegin]);
        int index = dis[preorder[preBegin]];

        root->left = dfs(preorder, preBegin+1, preBegin+1+(index-inBegin), inorder, inBegin, index);
        root->right = dfs(preorder, preBegin+1+(index-inBegin), preEnd, inorder, index+1, inEnd);
        return root;
    }
    
    void Postorder(TreeNode* root){
        if(root == NULL)	return;
        Postorder(root->left);
        Postorder(root->right);
        cout<<root->val<<' ';
    }
};

2. 已知前序和后序遍历不能重建二叉树

已知前序遍历结果和后序遍历结果，是不能确定一颗二叉树。

前序和后序在本质上都是将父节点与子结点进行分离，但并没有指明左子树和右子树的能力，因此得到这两个序列只能明确父子关系，而不能确定一个二叉树。

比如：前序序列1、3、6和 后序序列6、3、1。可以确定1是根节点，但是接下来的结果可能是多种的

3. 已知中序和后序遍历能重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

中序遍历 inorder = [9,3,15,20,7]

后序遍历Postorder = [15, 7, 9, 20, 3]

返回二叉树的前序遍历 preorder = [3,9,20,15,7]

限制：

0 <= 节点个数 <= 5000

递归

本题直接利用的是二叉树中序遍历和后序遍历的特点，通过递归来求解出答案。

1. 根据后序序列的最后一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在后序序列中确定左右子树的后序序列；
4. 由左子树的后序序列和中序序列建立左子树；
5. 由右子树的后序序列和中序序列建立右子树。

/**
 * 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 {
private:
    map<int, int> dis;      //巧妙借助了map，提高检索性能，缩短时间
public:
    void PostorderTraversal(vector<int>& inorder, vector<int>& postorder) {
        for(int i = 0; i < inorder.size(); i++){
            dis[inorder[i]] = i;
        }						 //第一步存map，优化检索
        TreeNode* root = dfs(inorder, 0, inorders.size(), postorder, 0, postorder.size());					//第二步递归重建二叉树(关键！)
        Preorder(root);		 	 //第三步递归前序遍历二叉树
    }

    TreeNode* dfs(vector<int>& inorder, int inBegin, int inEnd, vector<int>& postorder, int postBegin, int postEnd){
        if(inBegin >= inEnd || postBegin >= postEnd){
            return nullptr;
        }
        TreeNode* root = new TreeNode(postorder[postEnd]);
        int index = dis[postorder[postEnd]];

        root->left = dfs(inorder, inBegin, index-1, postorder, postBegin, postBegin + (index - inBegin -1));
        root->right = dfs(inorder, index + 1, inEnd, postorder, postBegin + (index - inBegin), postEnd - 1);
        return root;
    }
    
    void Preorder(TreeNode* root){
        if(root == NULL)	return;
        cout<<root->val<<' ';
        Preorder(root->left);
        Preorder(root->right);
    }
};