一, 题目说明
题目 105. Construct Binary Tree from Preorder and Inorder Traversal, 给二叉树的前序和中序遍历序列, 构造一棵二叉树. 题目难度是 Medium!
二, 我的解答
这个题目数据结构上面也有讲, 这里用递归遍历算法. 前序遍历第 1 个为树的根, 然后用根将中序遍历分成左右子树, 再递归就可以了.
代码如下:
- class Solution{
- public:
- TreeNode* createTree(vector<int> & preorder,vector<int>& inorder,int leftStart,int leftEnd){
- //preorder 中当前元素为树根
- TreeNode* r = new TreeNode(preorder[curRoot]);
- int k=leftStart;
- while(inorder[k] !=preorder[curRoot]) k++;
- curRoot++;
- if(k>leftStart){
- r->left = createTree(preorder,inorder,leftStart,k-1);
- }
- if(k<leftEnd){
- r->right = createTree(preorder,inorder,k+1,leftEnd);
- }
- return r;
- }
- TreeNode* buildTree(vector<int>& preorder,vector<int>& inorder){
- int len = preorder.size();
- if(preorder.size()<1) return NULL;
- TreeNode* root = new TreeNode(preorder[0]);
- if(len==1) return root;
- int k=0;
- while(inorder[k] !=preorder[0]) k++;
- curRoot = 1;
- if(k>0){
- root->left = createTree(preorder,inorder,0,k-1);
- }
- if(k<len-1){
- root->right = createTree(preorder,inorder,k+1,len-1);
- }
- return root;
- }
- private:
- int curRoot;
- };
性能如下:
- Runtime: 24 ms, faster than 44.15% of C++ online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
- Memory Usage: 22.2 MB, Less than 9.52% of C++ online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
三, 优化措施
代码简化如下:
- class Solution{
- public:
- TreeNode* createTree(vector<int> & preorder,vector<int>& inorder,int leftStart,int leftEnd){
- TreeNode* r = new TreeNode(preorder[curRoot]);
- int k=leftStart;
- while(inorder[k] !=preorder[curRoot]) k++;
- curRoot++;
- if(k>leftStart){
- r->left = createTree(preorder,inorder,leftStart,k-1);
- }
- if(k<leftEnd){
- r->right = createTree(preorder,inorder,k+1,leftEnd);
- }
- return r;
- }
- TreeNode* buildTree(vector<int>& preorder,vector<int>& inorder){
- int len = preorder.size();
- if(len<1) return NULL;
- curRoot = 0;
- return createTree(preorder,inorder,0,len-1);
- }
- private:
- int curRoot;
- };
- Runtime: 20 ms, faster than 64.01% of C++ online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
- Memory Usage: 22.4 MB, Less than 9.52% of C++ online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
来源: http://www.bubuko.com/infodetail-3448552.html