LeetCood:重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof

思路：

首先如果要构建一棵树我们是否要找到树的根节点然后找到左子树、右子树，然后再从左、右子树分别找到根节点，再分为左右子树，一直重复这个行为直到没有元素为止，这就是分治的思想，将大的问题分为小的相同的问题。再总结一下前序遍历和中序遍历的特点，在前序遍历中根节点肯定是排在树（完整序列）的首位或者子树（子序列）的首位，而中序遍历根节点肯定是排在树（完整序列）的中间或者子树（子序列）的中间，这样得出前序遍历可以方便为我们找到根节点，而中序遍历方便为我们找到左、右子树，然后再从左子树，右子树中继续上述操作，我们就递归构建出一颗树了。

代码题解：

#include<iostream>
#include <unordered_map>
#include<vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//中序遍历值和索引的映射关系
unordered_map<int, int> index;

/*
p_left 前序遍历（子）序列的首元素，p_right 前序遍历的尾元素，i_left 中序遍历的首元素，i_right 中序遍历的尾元素
*/
TreeNode* recursiveTree(vector<int>& preorder, vector<int>& inorder, int p_left, int p_right, int i_left, int i_right) {
    if (p_left > p_right)
    {
        return nullptr;
    }
    int root_value = preorder[p_left];//根的值一定是前序遍历子）序列的首元素
    int root_index = index[root_value]; //根据根的值我们找到根在中序遍历的索引，那么索引左侧则为左子树，右侧则为右子树
    TreeNode * root = new TreeNode(root_value); //new一个当前找到的节点
    int size_left_tree = root_index - i_left; // 根在中序遍历的索引减去中序遍历的首元素的位置 = 左子树的大小
    root->left = recursiveTree(preorder, inorder, p_left + 1, p_left + size_left_tree, i_left, root_index - 1);//递归左子树，并让当前节点的左子树指向递归结果
    root->right = recursiveTree(preorder, inorder, p_left + size_left_tree + 1, p_right, root_index + 1, i_right);//递归右子树
    return root;
}

/*
构建树
*/
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    for (int i = 0; i < inorder.size(); i++)
    {
        index[inorder[i]] = i;
    }
    return recursiveTree(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
}
int main() {
    //自行添加测试用例
    
    return 0;
}