题意分析

• 给出一个二叉树的先序遍历的序列和中序遍历的序列，需要我们对重建这棵二叉树。返回这个二叉树的根节点即可。
• 前置知识，我们首先需要知道什么是先序，后序和中序遍历。对于一个二叉树，我们按照根，左节点，右节点的顺序遍历就是先序遍历。按照左边节点，中间节点和右边节点的顺序就是后序遍历，按照左节点，右边节点和中间节点的序列遍历就是中序遍历。
• 如下图

解法分析

解法一

• 我们可以利用先需遍历和中序遍历的顺序，我们先找出这个二叉树的中序遍历序列里面中间节点，也可以说是一个根节点。然后，我么就可以知道这个二叉树的左右子树了，然后，我们先对左右子树进行重建，重建之后就会返回我们的得到我们的左右结点，然后接上去就行了。

• 如图

• 代码如下

  • 我们发现，不管怎么遍历，我们都必须要遍历这棵树的所有的结点的信息，$T(n)=2T(n\mathrm{/}2)+O(1)+O(n)T(n)=2T(n/2)+O(1)+O(n)$,所以时间复杂度为$O(nlogn)O(nlogn)$
  • 需要存储这棵树的所有的结点，空间复杂度为$O(n)O(n)$

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* root;
    // 定义一个全局变量，减少参数的传递
    vector<int> p,i;
    TreeNode* build(int lp,int rp,int lv,int rv){
        // 不满足区间的情况
        if(lp>rp) return NULL;
        TreeNode* now=new TreeNode(p[lp]);
        int index=lv;  // 这个变量用来查找在中序遍历里面根节点的下标
        while(index<=rv&&p[lp]!=i[index]){
            index++;
        }
        int len=index-lv;
        // 递归查找左节点
        now->left=build(lp+1,lp+len,lv,index-1);
        // 递归查找右节点
        now->right=build(lp+len+1,rp,index+1,rv);
        return now;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        p=pre,i=vin;
        TreeNode* root=build(0,pre.size()-1,0,vin.size()-1);
        return root;
    }
};

解法二

• 对于第二种写法，相对来说比第一种写法更加简洁，但是想对于第一种写法来说更难理解。我们就在原函数的基础上面进行递归的操作。但是这种写法中间需要开很多个动态的数组，空间浪费比较大。

• 代码如下

  • 我们这个方法只需要在原来的函数上进行修改，但是还是必须要遍历树的所有的结点。时间复杂度为O(n）
  • 需要存储树的所有的结点，空间复杂度为O(n)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        // 判断这个二叉树的节点是否已经是叶子节点了
        if(pre.size()==0||vin.size()==0){
            return NULL;
        }
        // 不是叶子节点就进行向下递归的操作
        TreeNode* root=new TreeNode(pre[0]);
        for(int i=0;i<vin.size();i++){
            // 找到和当前的先序遍历的头节点权值一样的节点
            if(root->val==vin[i]){
                // 找到之后就利用中序遍历的序列将这个序列分为左右子序列
                vector<int> pre1,pre2,vin1,vin2;
                for(int j=1;j<i+1;j++){
                    pre1.push_back(pre[j]);
                }
                for(int j=0;j<i;j++){
                    vin1.push_back(vin[j]);
                }
                for(int j=i+1;j<pre.size();j++){
                    pre2.push_back(pre[j]);
                }
                for(int j=i+1;j<vin.size();j++){
                    vin2.push_back(vin[j]);
                }
                // 进行递归的操作
                root->left=reConstructBinaryTree(pre1,vin1);
                root->right=reConstructBinaryTree(pre2,vin2);
                break;
            }
        }
        return root;
    }
};