1.前序和中序

#include <vector>
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        // write code here
        int p = preOrder.size();
        int v = vinOrder.size();

        if(p == 0 || v == 0) return nullptr;

        TreeNode* root = new TreeNode(preOrder[0]);
        //前序和中序 注意最右边的边界值
        for(int i = 0; i < vinOrder.size(); i++){
            if(preOrder[0] == vinOrder[i]){
                vector<int> leftPre(preOrder.begin() + 1,preOrder.begin() + i + 1);
                vector<int> leftVin(vinOrder.begin(),vinOrder.begin() + i);
                root->left = reConstructBinaryTree(leftPre, leftVin);

                vector<int> rightPre(preOrder.begin() + i + 1,preOrder.end());
                vector<int> rightVin(vinOrder.begin() + i + 1,vinOrder.end());
                root->right = reConstructBinaryTree(rightPre, rightVin);
                break;
            }
        }
        return root;
    }
};

算法思想：

根据前序遍历和中序遍历的特点，可以确定根节点以及左子树和右子树的前序遍历和中序遍历序列。通过递归的方式，不断构建子树，最终构建出整个二叉树。

时间复杂度：

假设二叉树中共有n个节点，每次递归都需要遍历一次中序遍历序列来确定根节点的位置，所以时间复杂度为O(n)。

空间复杂度：

递归过程中需要创建新的vector来存储子树的前序遍历和中序遍历序列，所以空间复杂度为O(n)。

2.中序和后序

#include <vector>
class Solution {
  public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // write code here
        int in = inorder.size();
        int po = postorder.size();

        if (in == 0 || po == 0) return nullptr;

        TreeNode* root = new TreeNode(postorder[po - 1]);
        //中序+后序 注意最左边的边界值；>=0
        for (int i = po - 1, j = 0; i >= 0; i--, j++) {
            if (postorder[po - 1] == inorder[i]) {

                vector<int> leftPost(postorder.begin(), postorder.end() - j - 1);
                vector<int> leftIn(inorder.begin(), inorder.end() - j - 1);
                root->left = buildTree(leftIn, leftPost);

                vector<int> rightPost(postorder.end() - 1 - j, postorder.end() - 1);
                vector<int> rightIn(inorder.end() - j, inorder.end());
                root->right = buildTree(rightIn, rightPost);

                break;
            }
        }
        return root;
    }
};

算法思想：

根据中序遍历和后序遍历的特点，可以确定根节点以及左子树和右子树的中序遍历和后序遍历序列。通过递归的方式，不断构建子树，最终构建出整个二叉树。

时间复杂度：

假设二叉树中共有n个节点，每次递归都需要遍历一次中序遍历序列来确定根节点的位置，所以时间复杂度为O(n)。

空间复杂度：

递归过程中需要创建新的vector来存储子树的中序遍历和后序遍历序列，所以空间复杂度为O(n)。

3.区别与联系

区别：

1. 前序遍历和中序遍历是根据根节点的位置来确定左子树和右子树的，而中序遍历和后序遍历是根据根节点的位置来确定左子树和右子树的。

2. 前序遍历和中序遍历可以唯一确定一棵二叉树，中序遍历和后序遍历也可以唯一确定一棵二叉树。

联系：

1. 两种方法都是根据根节点的位置来确定左子树和右子树的。

2. 两种方法都是通过递归的方式来构建整个二叉树。

总结：

前序遍历和中序遍历可以唯一确定一棵二叉树，中序遍历和后序遍历也可以唯一确定一棵二叉树。两种方法都是通过递归的方式来构建二叉树，只是确定左子树和右子树的方式不同。一个模子刻出来的，利用vector来进行操作的haul但请注意二者左右边界值！！