輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果但惶，請重建該二叉樹阴汇。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字页响。
例如非洲，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
3
/ \
9 20
/ \
15 7
限制：
0 <= 節(jié)點個數(shù) <= 5000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
思路：
首先如果要構(gòu)建一棵樹我們是否要找到樹的根節(jié)點然后找到左子樹、右子樹俯画，然后再從左析桥、右子樹分別找到根節(jié)點，再分為左右子樹艰垂，一直重復(fù)這個行為直到?jīng)]有元素為止泡仗，這就是分治的思想，將大的問題分為小的相同的問題猜憎。再總結(jié)一下前序遍歷和中序遍歷的特點娩怎，在前序遍歷中根節(jié)點肯定是排在樹（完整序列）的首位或者子樹（子序列）的首位，而中序遍歷根節(jié)點肯定是排在樹（完整序列）的中間或者子樹（子序列）的中間胰柑，這樣得出前序遍歷可以方便為我們找到根節(jié)點截亦，而中序遍歷方便為我們找到左爬泥、右子樹，然后再從左子樹崩瓤，右子樹中繼續(xù)上述操作袍啡，我們就遞歸構(gòu)建出一顆樹了。
代碼題解：
#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) {}
};
//中序遍歷值和索引的映射關(guān)系
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]; //根據(jù)根的值我們找到根在中序遍歷的索引肾扰，那么索引左側(cè)則為左子樹畴嘶，右側(cè)則為右子樹
TreeNode * root = new TreeNode(root_value); //new一個當(dāng)前找到的節(jié)點
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);//遞歸左子樹，并讓當(dāng)前節(jié)點的左子樹指向遞歸結(jié)果
root->right = recursiveTree(preorder, inorder, p_left + size_left_tree + 1, p_right, root_index + 1, i_right);//遞歸右子樹
return root;
}
/*
構(gòu)建樹
*/
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;
}
