[剑指Offer]7-重建二叉树
2024-08-30 07:14:19
链接
题意
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解题思路
递归。
其中，在找前序遍历的左右子树分割点时，用中序遍历的左右子树节点数直接找。
注意，只有各节点取值均不相同时，才能重建二叉树。
相关
用一个vector给另一个vector赋值，用vector的构造函数vector<int> rightVin(it+1,vin.end());
获取vector首节点vec.front()
代码
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.empty()||vin.empty()||pre.size()!=vin.size()){
return nullptr;
}
TreeNode* pRoot=new TreeNode(pre.front());
if(pre.size()!=1){
vector<int>::iterator it=find(vin.begin(),vin.end(),pre.front());
vector<int> leftVin(vin.begin(),it);
vector<int> rightVin(it+1,vin.end());
vector<int>::iterator splitIt=pre.begin()+leftVin.size()+1;
vector<int> leftPre(pre.begin()+1,splitIt);
vector<int> rightPre(splitIt,pre.end());
pRoot->left=reConstructBinaryTree(leftPre,leftVin);
pRoot->right=reConstructBinaryTree(rightPre,rightVin);
}
return pRoot;
}
};
最新文章
- 使用jQuery要注意的问题
- C#数组的排序（正序逆序）
- java获取本月开始时间和结束时间、上个月第一天和最后一天的时间以及当前日期往前推一周、一个月
- sqlplus时报Linux-x86_64 Error: 13: Permission denied
- Java [Leetcode 119]Pascal's Triangle II
- C#去除byte数组头尾杂质(即不需要的数据)
- 墙内安装nautilus-dropbox 1.6.0-2
- HBASE完全分布式模式的安装
- spring security：ajax请求的session超时处理
- Sublime安装Package Control插件
- Java过滤敏感词语/词汇---DFA算法
- 四种途径提高RabbitMQ传输数据的可靠性（二）
- Windows平台下结合 tortoiseSVN 和 VisualSVN Server 搭建SVN服务器并实现 web 站点同步
- Hibernate Transformers之三种结果转换说明
- 配置Nginx反向代理WebSocket，以代理noVNC为例
- spring中的bean的属性scope
- CPU单核多核区别【转载】
- __MySQL 5.7 Replication 相关新功能说明
- Maven存储库
- RMAN：简单的duplicate创建新数据库