题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路

• 二叉树的前序遍历序列的第一个元素就是树的根节点的值
• 中序遍历中，根节点的左边就是它的左子树，右边就是它的右子树
• 对于每一个左右子树都有如上规则——信息就是根节点

采用递归方法

流程

（1）创建根节点，根节点的值为先序遍历序列的第一个元素
（2）找根节点在中序中的位置
（3）取出左子树的先序序列和中序序列；右子树的先序序列和中序序列
（4）根节点的左子树和右子树采用递归进行建立——信息就是根节点（每次都能得到一个根节点）

代码

/**
 * 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)
            return NULL;    //若遍历序列为空，则树也为空
        TreeNode* root = new TreeNode(pre[0]);  //根节点的值为先序遍历的第一个值
        vector<int> left_pre,left_vin,right_pre,right_vin;  //定义左子树的先序、中序遍历序列和右子树的先序、中序遍历序列
        int pos=0;
        while(vin[pos]!=pre[0])   //找根节点在中序中的位置:pos
            pos++;
        for(int i=0;i<pos;i++)   //左子树的先序序列和中序序列
        {
            left_pre.push_back(pre[i+1]);
            left_vin.push_back(vin[i]);
        }
        for(int i=pos+1;i<pre.size();i++)  //右子树的先序序列和中序序列
        {
            right_pre.push_back(pre[i]);
            right_vin.push_back(vin[i]);
        }
        root->left=reConstructBinaryTree(left_pre,left_vin);  //对每一棵左子树也进行同样的操作
        root->right=reConstructBinaryTree(right_pre,right_vin); //对每一棵右子树也进行同样的操作
        return root;
    }
};