<span>重建二叉树</span>

题目描述

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
 
 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
13         if(pre.empty() || in.empty())
14             return NULL;
15         return ConstructBinaryTree(pre.begin(),pre.end()-1,in.begin(),in.end()-1);
16     }
17     struct TreeNode* ConstructBinaryTree
18     (vector<int>::iterator startPre,vector<int>::iterator endPre,
19      vector<int>::iterator startIn,vector<int>::iterator endIn){
20         int rootValue = *startPre;
21         TreeNode* root = new TreeNode(rootValue);
22         if(startPre == endPre){
23             if(startIn == endIn && *startPre == *startIn)
24                 return root;
25             else
26                 return NULL;
27         }
28         vector<int>::iterator rootInOrder = startIn;
29         while(rootInOrder <= endIn && *rootInOrder != rootValue)
30             ++rootInOrder;
31         
32         if(rootInOrder == endIn && *rootInOrder != rootValue)
33             return NULL;
34         
35         int leftLength = rootInOrder - startIn;
36         vector<int>::iterator leftPreEnd = startPre + leftLength;
37         if(leftLength>0)
38             root->left = ConstructBinaryTree(startPre+1,leftPreEnd,startIn,rootInOrder-1);
39         if(leftLength < endIn - startIn)
40             root->right = ConstructBinaryTree(leftPreEnd+1,endPre,rootInOrder+1,endIn);
41         
42         return root;
43     }
44 };

 

全部评论

相关推荐

02-22 18:38
门头沟学院 Java
程序员牛肉:标准的NPC简历,一个短链接+12306。你可以在牛客上面搜一搜有多少人的简历和你一样。你自己能不能给出你一个理由让面试官在大家简历高度相同的情况下,选择约面你而不是对应的211,985学生? 是因为你即将拥有的那段小厂实习吗?这种小厂实习真的很有含金量吗?因此你可以找实习,但是你如果只能找到小厂实习的话,其实意义不太大。 但你的时间是充足的,相信我:从现在到今年的九月份大三上你就干两个事情:"写博客"+“参加开源之夏”。这两个搞好了不亚于一段大厂实习的含金量。 想要让自己变得更强,首先就是不要把自己当打工人看待,让自己简历上面的活人气息更多一点,不要让自己成为流水线的产物。你不是在出售你的技能,你是在利用你的技能和公司达成一种合作关系。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务