注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex106 Construct Binary Tree from Inorder and Postorder Traversal  

2015-05-19 22:54:42|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
从后序遍历和中序遍历中重建二叉树,和ex105相似的思路。

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

如果序列中没有重复元素的话,后序遍历的最后一个节点肯定是root节点,而倒数第二个节点肯定是右子树的root节点,依次递归,得到左右子树。见c代码

struct TreeNode* reConstruct(int* postorder, int postStart, int *postEnd, int* inorder, int inStart, int inEnd)
{
//postEnd这个指针在递归过程中需要一直递减,且全局有效
if (inStart == inEnd)
{
struct TreeNode* current = (struct TreeNode*)malloc(sizeof(struct TreeNode));
//只剩下一个了
current->val = postorder[postEnd[0]];
current->left = NULL;
current->right = NULL;
postEnd[0]--;
return current;
}
else
{
//后序遍历的第最后一个元素肯定是当前的根节点 查找该节点在中序遍历的位置
int keyValue = postorder[postEnd[0]];
int i;
int index = 0;
for (i = inStart; i <= inEnd; i++)
{
if (keyValue == inorder[i])
{
index = i;
break;
}
}
//index左边是左子树的中序遍历,index的右边是右子树的中序列遍历

struct TreeNode* current = NULL, *left = NULL, *right = NULL;
current = (struct TreeNode*)malloc(sizeof(struct TreeNode));
current->val = keyValue;
postEnd[0]--;

//这个地方递归左右子树的顺序和ex105 通过先序+中序 重构树的顺序不一样
//可以简单推一下,对于后序遍历keyValue的后面一个值肯定是右子树的keyValue
//递归右子树
if ((index + 1) <= inEnd)
{
//判定右边是否还有值
right = reConstruct(postorder, postStart, postEnd, inorder, index + 1, inEnd);
}
else
{
//如果右边没有值的话,那right直接就赋值为空
right = NULL;
}

//递归左子树
if ((index - 1) >= inStart)
{
//判定左边是否还有值
left = reConstruct(postorder, postStart, postEnd, inorder, inStart, index - 1);
}
else
{
//如果左边没有值的话,那left直接就赋值为空
left = NULL;
}


current->right = right;
current->left = left;
return current;
}
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
//调用reConstruct进行递归
if (postorderSize <= 0)
{
return NULL;
}
struct TreeNode* root = NULL;
int postStart = 0, postEnd = postorderSize - 1;
int inStart = 0, inEnd = postorderSize - 1;
root = reConstruct(postorder, postStart, &postEnd, inorder, inStart, inEnd);
return root;
}



  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017