面试题7：重建二叉树

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

思路1：前序序列第一个节点即为二叉树的根节点，以此根节点为中序序列中的分界点，分离出左子树和右子树，递归创建二叉树。

代码：

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        //若前序和中序为空，则返回空树
        if(pre.empty()||vin.empty())
            return NULL;
        //创建根节点
        TreeNode *tRoot=new TreeNode(pre[0]);
        //在中序序列中找到根节点的位置，并记录左子树节点的数量
        int num_lchild;
        for(int i=0;i<vin.size();i++)
        {
            if(vin[i]==pre[0])
            {
                num_lchild=i;
                break;
            }
        }
        //若找到最后都没有找到对应的根节点，说明输入序列有问题
        if(vin[num_lchild]!=pre[0])
            return NULL;

        //若找到，则可以根据此根节点划分左右子树
        //递归构造左右子树
        vector<int> left_pre,right_pre,left_in,right_in;
        for(int i=0;i<num_lchild;i++)
        {
            left_pre.push_back(pre[i+1]);
            left_in.push_back(vin[i]);
        }
        for(int i=num_lchild+1;i<vin.size();i++)
        {
            right_pre.push_back(pre[i]);
            right_in.push_back(vin[i]);
        }
        //递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点
        tRoot->left=reConstructBinaryTree(left_pre,left_in);
        tRoot->right=reConstructBinaryTree(right_pre,right_in);
        return tRoot;
    }
};

注意几点：

特殊处理：取根节点之前，判断前序和中序序列是否为空，若为空则返回空树；
取根节点之后，遍历中序序列找出根节点的位置时，出现找不到对应节点的情况。
创建根节点时：TreeNode *tRoot=new TreeNode(pre[0]);里面的pre[0]相当于初始化tRoot->value=pre[0]的意思，具体情况根据节点定义确定。
构造左右子树前中序序列时注意区间划分。
别忘了返回值return tRoot.

2.递归算法：

思路都一样

TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
        if (pre.size() == 0 || vin.size() == 0)
            return nullptr;
        return reConstructBinaryTree(pre, 0, pre.size() - 1, vin,  0, vin.size() - 1);
    }

    TreeNode* reConstructBinaryTree(vector<int> &pre, int begin_pre, int end_pre,  vector<int> &vin, int begin_vin, int end_vin)
    {
        if (begin_pre>end_pre||begin_vin > end_vin)
            return nullptr;
        int rootVal = pre[begin_pre];
        TreeNode* root = new TreeNode(rootVal);
        int in = begin_vin;
        while (vin[in]!=rootVal&&in<=end_vin)
        {
            ++in;
        }
        //根据在中序找到的根节点，可以判断出左子树的元素个数为in-begin_vin。由此可以得出左右子树的起始点和终点
        root->left = reConstructBinaryTree(pre, begin_pre + 1, begin_pre + in-begin_vin, vin, begin_vin, in - 1);
        root->right = reConstructBinaryTree(pre, begin_pre + in + 1-begin_vin, end_pre, vin,in + 1, end_vin);
        return root;
    }