6
要求
时间限制:1秒 空间限制:32768K
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回
解题思路
解题的前提:两个序列中必须有一个中序序列
前(后)序序列用于提供根节点,根节点就是序列第一个元素(最后一个元素)
中序序列用于确定当前根节点的左右子树有哪些节点
如下图所示:
确定了左右子树有哪些元素之后就继续递归
代码
/*
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* reConstructBinaryTree(vector<int> pre,vector<int> vin)
{
int psize=pre.size();
int vsize=vin.size();
if(psize==0 || vsize==0 || psize != vsize)
return NULL;
return reBuildBinaryTreeCore(pre, 0, psize-1, vin, 0, vsize-1);
}
TreeNode* reBuildBinaryTreeCore(vector<int>& pre, int startIdxOfP, int endIdxOfP,
vector<int>& vin, int startIdxOfV, int endIdxOfV)
{
int valOfRoot = pre[startIdxOfP];
TreeNode* root = new TreeNode(valOfRoot);
if(startIdxOfP == endIdxOfP)
{
if(startIdxOfV == endIdxOfV)
return root;
else
{
cout << "无效输入" << endl;
abort();
}
}
else
{
int idxOfRootInV = 0;
for(idxOfRootInV = startIdxOfV;idxOfRootInV <= endIdxOfV &&
vin[idxOfRootInV] != valOfRoot;++idxOfRootInV)
{
}
if(vin[idxOfRootInV] != valOfRoot)
{
cout << "无效输入" << endl;
abort();
}
int leftLength = idxOfRootInV - startIdxOfV;
//左
if(startIdxOfV <= idxOfRootInV - 1)
root->left = reBuildBinaryTreeCore(pre,
startIdxOfP + 1,
startIdxOfP + leftLength,
vin,
startIdxOfV,
idxOfRootInV - 1);
//右
if(idxOfRootInV + 1 <= endIdxOfV)
root->right = reBuildBinaryTreeCore(pre,
startIdxOfP + 1 + leftLength,
endIdxOfP,
vin,
idxOfRootInV+1,
endIdxOfV);
}
return root;
}
};
由于还要搬砖,没有办法一一回复私信把学习资料发给大家。我直接整理出来放在下面,觉得有帮助的话可以下载下来用于学习
链接:https://pan.baidu.com/s/1C-9TE9ES9xrySqW7PfpjyQ 提取码:cqmd
感谢各位人才的点赞、收藏、关注
微信搜「三年游戏人」收获一枚有情怀的游戏人,第一时间阅读最新内容,获取优质工作内推
原文地址:http://www.cnblogs.com/gamemanthree/p/16856311.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性