题解 | #重建二叉树#

方法：递归

对于二叉树的前序遍历，我们知道序列的第一个元素必定是根节点的值，因为序列没有重复的元素，因此中序遍历中可以找到相同的这个元素，而我们又知道中序遍历中根节点将二叉树分成了左右子树两个部分。

具体做法：

step 1：先根据前序遍历第一个点建立根节点。

step 2：然后遍历中序遍历找到根节点在数组中的位置。

step 3：再按照子树的节点数将两个遍历的序列分割成子数组，将子数组送入函数建立子树。

step 4：直到子树的序列长度为0，结束递归。

时间复杂度：o(n)。

空间复杂度：o(n)。

class Solution {
  public:
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        if (preOrder.size() == 0 || vinOrder.size() == 0)
            return nullptr;
        TreeNode* head = new TreeNode(preOrder[0]);

        for (int i = 0; i < vinOrder.size(); i++) {
		  	//获取前序遍历第一个结点在中序遍历中的位置
            if (vinOrder[i] == preOrder[0]) {
                //左子树
                vector<int> leftvin(vinOrder.begin(), vinOrder.begin() + i);
                vector<int> leftpre(preOrder.begin() + 1, preOrder.begin() + i + 1);
                head->left = reConstructBinaryTree(leftpre, leftvin);
                //右子树
                vector<int> rightvin(vinOrder.begin() + i + 1, vinOrder.end());
                vector<int> rightpre(preOrder.begin() + i + 1, preOrder.end());
                head->right = reConstructBinaryTree(rightpre, rightvin);
            }
        }

        return head;
    }
};