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

HT·生活

123

 
 
 

日志

 
 

ex105 Construct Binary Tree from Preorder and Inorder Traversal  

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

  下载LOFTER 我的照片书  |
从先序遍历和中序遍历中重建树

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

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

这个和ex106是一个思路,因为先序遍历的话第一个key,肯定是root节点,然后preorder的下一个节点就是,root的左子树的root节点,依次递归,就能重建左右子树了。见c代码

struct TreeNode* reConstruct(int* preorder, int *preStart, int preEnd, int* inorder, int inStart, int inEnd)
{
if (inStart == inEnd)
{
struct TreeNode* current = (struct TreeNode*)malloc(sizeof(struct TreeNode));
//只剩下一个了
current->val = preorder[preStart[0]];
current->left = NULL;
current->right = NULL;
preStart[0]++;
return current;
}
else
{
//先序遍历的第一个元素肯定是当前的根节点 查找该节点在中序遍历的位置
int keyValue = preorder[preStart[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;
preStart[0]++;
//递归左子树
if ((index - 1) >= inStart)
{
//判定左边是否还有值
left = reConstruct(preorder, preStart, preEnd, inorder, inStart, index - 1);
}
else
{
//如果左边没有值的话,那left直接就赋值为空
left = NULL;
}

//递归右子树
if ((index + 1) <= inEnd)
{
//判定右边是否还有值
right = reConstruct(preorder, preStart, preEnd, inorder, index + 1, inEnd);
}
else
{
//如果右边没有值的话,那right直接就赋值为空
right = NULL;
}
current->right = right;
current->left = left;
return current;
}
}

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


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

历史上的今天

评论

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

页脚

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