首页 > 代码库 > 前序和中序构造树的递归实现
前序和中序构造树的递归实现
虽然有时候递归的效率不高,但可以化繁为简使做题的效率大大提高。是程序设计重要的一术要熟练掌握 。
就本题来说,最重要的的包括三个方面:
(1)如何设计递归体
(2)递归参数如何传递
(3)递归出口怎眼写才能使程序简化
首先,递归体的形式决定了能否较为简单的完成程序,如果细节考虑得过于繁琐,则即使用了递归程序也会写的很痛苦。因为你把本来该电脑自动完成的任务过多得交给了自己。所以,动笔之前,一定要做好顶层设计。本题设计了两个unordered_map以迅速确定子树的范围,并将其设为全局以免参数传递的麻烦。
其次,传什么,怎么传?递归体设计好后穿什么就确定了。比较大的实体可以引用的方式传递,如过程无修改再加上const。
最后,如果确定递归出口。一定要想到最简的方式,避免过分地处理细节。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode *sub(vector<int> &preorder, int pre1,int pre2,vector<int> &inorder,int in1,int in2){ if(pre2<pre1) return nullptr; <span style="white-space:pre"> </span>//very important to assure when the recursion ends TreeNode *root = new TreeNode(preorder[pre1]); //inorder ranges int l1=in1, l2=in[preorder[pre1]]-1; int r1=l2+2, r2=in2; //preoder ranges int ll=pre1+1, lr=pre1+1+(l2-l1); // l2-l1,length of left subtree int rl=lr+1, rr=pre2; root->left=sub(preorder,ll,lr,inorder,l1,l2); root->right=sub(preorder,rl,rr,inorder,r1,r2); return root; } TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { if(!preorder.size()||!inorder.size()) return nullptr; if(preorder.size()!=inorder.size()) return nullptr; //pre-processing for(int i=0 ; i< preorder.size();++i) pre[preorder[i]]=i; for(int i=0 ; i< inorder.size();++i) in[inorder[i]]=i; int n=preorder.size()-1; TreeNode *root=sub(preorder,0,n,inorder,0,n); return root; } public: unordered_map<int,int> pre,in; };
前序和中序构造树的递归实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。