输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 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;
}
网友评论