LeetCode（132）
算法（208）
Total Accepted: 7041 Total Submissions: 27696 My Submissions
Given preorder and inorder traversal of a tree, construct the binary tree.
You may assume that duplicates do not exist in the tree.
Total Accepted: 6863 Total Submissions: 26686 My Submissions
Given inorder and postorder traversal of a tree, construct the binary tree.
You may assume that duplicates do not exist in the tree.
根据前序遍历和中序遍历建树以及根据中序遍历和后序遍历建树。
基本思想是递归，需要注意的是边界的处理。
关于前序遍历和后序遍历建树，树是不唯一的，在已有详细说明，请参考。
* Definition for binary tree
* public class TreeNode {
TreeNode(int x) { val = }
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
if (inorder == null || inorder.length == 0) {
int len1 = preorder.length - 1;
int len2 = inorder.length - 1;
if (len1 != len2) {
return dfs(preorder, inorder, 0, len2, 0);
private TreeNode dfs(int[] preorder, int[] inorder, int low,
int high, int index) {
if (low & high) {
TreeNode node = new TreeNode(preorder[index]);
if (low == high) {
int pos = searchInsert(inorder, preorder[index], low, high);
node.left = dfs(preorder, inorder, low, pos - 1, index + 1);
node.right = dfs(preorder, inorder, pos + 1, high, index + 1 + (pos - low));
private int searchInsert(int[] array, int t, int low, int high) {
int pos = 0;
for (int i = i &= i++) {
if (array[i] == t) {
* Definition for binary tree
* public class TreeNode {
TreeNode(int x) { val = }
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || inorder.length == 0) {
if (postorder == null || postorder.length == 0) {
int len1 = inorder.length - 1;
int len2 = postorder.length - 1;
if (len1 != len2) {
return dfs(inorder, postorder, 0, len1, len2);
private TreeNode dfs(int[] inorder, int[] postorder, int low,
int high, int index) {
if (low & high) {
TreeNode node = new TreeNode(postorder[index]);
if (low == high) {
int pos = searchInsert(inorder, postorder[index], low, high);
node.left = dfs(inorder, postorder, low, pos - 1, index - 1 - (high - pos));
node.right = dfs(inorder, postorder, pos + 1, high, index - 1);
private int searchInsert(int[] array, int t, int low, int high) {
int pos = 0;
for (int i = i &= i++) {
if (array[i] == t) {
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：212505次
积分：4716
积分：4716
排名：第4995名
原创：262篇
转载：16篇
评论：47条
文章：102篇
阅读：64927
文章：121篇
阅读：101515
(2)(1)(1)(1)(3)(2)(7)(6)(2)(1)(5)(3)(9)(1)(2)(5)(2)(14)(10)(18)(25)(32)(18)(35)(74)二叉树（已知先序和中序求后序） - 简书
二叉树（已知先序和中序求后序）
我们可以在先序遍历中找到根节点的编号，在中序遍历中我们找到根节点所在的位置，那么前面的节点就是根节点的左子树上的节点，后面的节点就是柚子树上的节点。按照以上方法使用递归可以建立一个二叉树函数调用示意图：怎么用先序序列和中序序列来做一个二叉树_c++吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：275,997贴子：
怎么用先序序列和中序序列来做一个二叉树收藏
c++海同强大的师资阵容,因人制定课程内容,分阶段学习.c++就到正规IT技术培训机构-海同科技,培训IT技术面对面教学,免费重读!
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或leetcode（43）
算法（61）
思路：先序的第一个元素和后序的最后一个元素是当前子树的根，然后遍历中序序列，找到左右子树的分界线，递归建左子树和右子树。
class Solution {
/*由于是oj，这里假设给的序列是合法的，正常情况是需要判断不合法情况的 */
TreeNode *buildTree(vector&int& &inorder, vector&int& &postorder,int instart,int inend,int poststart,int postend) {
TreeNode* root = new TreeNode(postorder[postend]);
if(instart == inend && poststart == postend && instart == poststart)
for(i =i &=++i)
if(inorder[i] == postorder[postend])//找到中序的根节点
if(i & instart)root -& left = buildTree(inorder,postorder,instart,i - 1,poststart,poststart + (i - instart - 1));
if(i & inend) root -& right = buildTree(inorder,postorder,i + 1,inend,poststart + i - instart,postend - 1);
TreeNode *buildTree(vector&int& &inorder, vector&int& &postorder) {
int inlength = inorder.size(),postlength = postorder.size();
if( inlength == 0 || inlength != postlength ) return NULL;
return buildTree(inorder,postorder,0,inlength-1,0,postlength-1);
class Solution {
TreeNode *buildTree(vector&int&& preorder,vector&int& &inorder,int prestart,int preend,int instart,int inend) {
TreeNode* root = new TreeNode(preorder[prestart]);
if(instart == inend && prestart == preend && instart == prestart)
for(i =i &=++i)
if(inorder[i] == preorder[prestart])//找到中序的根节点
if(i & instart)root -& left = buildTree(preorder,inorder,prestart+1,prestart + i - instart,instart,i - 1);
if(i & inend) root -& right = buildTree(preorder,inorder,prestart + i - instart + 1,preend,i + 1,inend);
TreeNode *buildTree(vector&int& &preorder, vector&int& &inorder) {
int prelength = preorder.size(),inlength = inorder.size();
if( inlength == 0 || inlength != prelength ) return NULL;
return buildTree(preorder,inorder,0,prelength-1,0,inlength-1);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(2964)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'二叉树的基本操作（先序、中序、后序、层次，求结点数，叶子树和深度）',
blogAbstract:'算法描述：
首先定义一个结构体类型的树存储结构，有数据域，指针有2个，分别指向左右孩子；
&&&&&&&& 先序建立一棵二叉树：采用递归算法，输入一个字符，递归结束的标志是if(ch == \'!\')；如果不为空则将字符存入数据域，然后分别是左孩子和右孩子；
&&&&&&&& 先序遍历：采用递归算法，结束标志是if(！T)；如果树不为空则输出根，然后是左孩子和孩子；
&&&&&&&& 中序遍历：采用递归算法，结束标志是if(！T)；如果树不为空左孩子，然后输出，再是右孩子；
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:1,
publishTime:9,
permalink:'blog/static/',
commentCount:0,
mainCommentCount:0,
recommendCount:2,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'',
hmcon:'1',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}