重构二叉树

重构二叉树分为两种，一种是根据前序和中序遍历序列重构；一种是根据中序和后序遍历序列重构。牛客网。

本文记录了根据前序遍历序列和中序遍历序列重构二叉树的解题思路以及相关的代码。

题目

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

前序+中序

二叉树的前序遍历顺序：根->左节点->右节点
二叉树的中序遍历顺序：左节点->根->右节点

因此，前序遍历序列中第一个节点为树的根节点，其后紧接着跟着左子树前序遍历序列+右子树前序遍历序列。而中序遍历序列中，根节点左侧为左子树中序遍历序列，右侧为右子树中序遍历序列。

从前序遍历序列中我们可以确定树的根节点，通过根节点的值在中序遍历序列中找到中序遍历序列中的根节点，继而可以找到根节点左子树上的节点数和右子树上的节点数。通过左右子树上的节点数可以在前序遍历序列中找出左右子树的前序遍历序列。通过递归，就可以构建出整个子树。

以题中的例子来说：

1 2	前序遍历序列：{1,2,4,7,3,5,6,8} 中序遍历序列：{4,7,2,1,5,3,8,6}

树的根节点为1，在中序遍历序列中可以发现根节点左侧有三个节点，也就是根节点的左子树上有三个节点；根节点右侧有四个节点，也就是根节点的右子树上有四个节点；因此可以找出左子树的前序遍历序列为{2,4,7}，右子树的前序遍历序列为{3,5,6,8}。递归处理即可。

/**
* 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 nullptr; }
        TreeNode *root = new TreeNode(pre[0]);
        auto v = std::find(vin.begin(), vin.end(), pre[0]);
        root->left = reConstructBinaryTree(vector<int>(pre.begin()+1, pre.begin()+1+(v-vin.begin())), vector<int>(vin.begin(), v));
        root->right = reConstructBinaryTree(vector<int>(pre.begin()+1+(v-vin.begin()), pre.end()) , vector<int>(v+1, vin.end()));
        return root;
    }
};