每日一题 剑指offer（重建二叉树）
编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化和锻炼自己的编程能力（最起码不会忘记编程）
特别说明：编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法，所以提供的代码不一定是最优解，但是本文提供的编程代码均为通过测试代码。
重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
二叉树的定义为：
1//Definition for binary tree
2struct TreeNode {
3 int val;
4 TreeNode *left;
5 TreeNode *right;
6 TreeNode(int x) : val(x),left(NULL), right(NULL) {}
7};
解析
先序遍历第一个位置肯定是根节点node，中序遍历的根节点位置在中间p，在p左边的肯定是node的左子树的中序数组，p右边的肯定是node的右子树的中序数组另一方面，先序遍历的第二个位置到p，也是node左子树的先序子数组，剩下p右边的就是node的右子树的先序子数组把四个数组找出来，分左右递归调用即可。
代码
1class Solution {
2public:
3 struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
4 int in_size = in.size();
5 if(in_size == 0)
6 return NULL;
7 vector<int> pre_left, pre_right, in_left, in_right;
8 int val = pre[0];
9 TreeNode* node = new TreeNode(val);//root node is the first element in pre
10 int p = 0;
11 for(p; p < in_size; ++p){
12 if(in[p] == val) //Find the root position in in
13 break;
14 }
15 for(int i = 0; i < in_size; ++i){
16 if(i < p){
17 in_left.push_back(in[i]);//Construct the left pre and in
18 pre_left.push_back(pre[i+1]);
19 }
20 else if(i > p){
21 in_right.push_back(in[i]);//Construct the right pre and in
22 pre_right.push_back(pre[i]);
23 }
24 }
25 node->left = reConstructBinaryTree(pre_left, in_left);
26 node->right = reConstructBinaryTree(pre_right, in_right);
27 return node;
28 }
29};
相关推荐
赞 (0)