剑指 Offer 07. 重建二叉树-7月22日
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了剑指 Offer 07. 重建二叉树-7月22日,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2299字,纯文字阅读大概需要4分钟。
内容图文
![剑指 Offer 07. 重建二叉树-7月22日](/upload/InfoBanner/zyjiaocheng/1047/3c49ba4948f0468b8027841d0774f7e0.jpg)
题目
剑指 Offer 07. 重建二叉树
我的思路
递归的思想来解决: 重复性的问题是: 输入preorder 和 inorder字符串 在inorder字符串中找到preorder首字符,把inorder字符串劈成2个子字符串 以inorder第一个子符串中的最后一个字符为边界,把preorder字符串也分成两个(用子字符串长度加上preorder第一个子串的起始位置即可) 再执行两次:create(root,pre1,in1);create(root,pre2,in2);
我的实现
/* * * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public : void create(TreeNode* root,int pre_begin,int pre_end,int in_begin,int in_end,vector<int>& preorder, vector<int>& inorder){ printf("%d\n",inorder[in_begin]); int root_val = preorder[pre_begin]; //root->val = root_val;if(pre_begin==pre_end) return;//递归出口条件 //在中序字符串中找到root_val,劈成两半int i,k,temp; int j = pre_begin; for(i=in_begin;i<=in_end;i++){ if(inorder[i]==root_val) break; } printf("i=%d\n",i); if(i>in_begin)//存在左子树 { //在前序子串中找到中序被劈开处前一个字符 temp = pre_begin; j = pre_begin+i-in_begin; root->left=new TreeNode(preorder[pre_begin+1]); printf("create:%d--%d,%d--%d",pre_begin+1,j,in_begin,i-1); create(root->left,pre_begin+1,j,in_begin,i-1,preorder,inorder); } if(i<in_end)//存在右子树 { //在前序子串中找到中序被劈开处后一个字符 root->right=new TreeNode(preorder[j+1]); create(root->right,j+1,pre_end,i+1,in_end,preorder,inorder); } } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if(preorder.size()==0)return NULL; TreeNode * root = new TreeNode(preorder[0]); //root->left=NULL;root->right=NULL; create(root,0,preorder.size()-1,0,preorder.size()-1,preorder,inorder); return root; } }; /* 递归的思想来解决: 重复性的问题是: 输入preorder 和 inorder字符串 在inorder字符串中找到preorder首字符,把inorder字符串劈成2个子字符串 以inorder第一个子符串中的最后一个字符为边界,把preorder字符串也分成两个(用子字符串长度加上preorder第一个子串的起始位置即可) 再执行两次:create(root,pre1,in1);create(root,pre2,in2); */
拓展学习
另一种思路(迭代)
转自官方题解
前序遍历的第一个元素是根,可以把中序遍历字符串劈开,分成左子树和右子树,很直观。
而中序遍历的第一个元素,是树的最左下节点。也可以看做是把前序遍历字符串劈开,分成从根一路左下到最左下节点 和 非这一路的子串。借助栈,处理!
比较难理解!
数组传参学会用迭代器
TreeNode* recursionBuild(vector<int>::iterator preBegin, vector<int>::iterator preEnd,vector<int>::iterator inBegin, vector<int>::iterator inEnd ) { ... recursionBuild(preBegin+1,preBegin+1+(root-inBegin),inBegin,root); ... }
原文:https://www.cnblogs.com/BoysCryToo/p/13362654.html
内容总结
以上是互联网集市为您收集整理的剑指 Offer 07. 重建二叉树-7月22日全部内容,希望文章能够帮你解决剑指 Offer 07. 重建二叉树-7月22日所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。