编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化和锻炼自己的编程能力(最起码不会忘记编程) 特别说明:编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法,所以提供的代码不一定是最优解,但是本文提供的编程代码均为通过测试代码。 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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};
|