重建二叉树C++实现
发布日期:2021-10-02 06:27:34
浏览次数:2
分类:技术文章
本文共 1020 字,大约阅读时间需要 3 分钟。
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
解题思路
对于任何一个二叉树,给定先序和中序,或者后序和先序的遍历结果,均可以构造出整个二叉树
本题给定了先序和中序,则求解思路为:
- 给定一个二叉树的先序遍历,第一个出现的结点为二叉树的根结点(我们计为
N
) - 则在中序遍历中,结点
N
左边的元素为根结点的左子树,结点N
右边的元素为根结点的右子树 - 对于左子树和右子树,我们同样可以使用上面的方法递归求解,则最终可以得到整个二叉树
代码实现
/** * 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 pre,vector vin) { if(pre.size()==0) return NULL; TreeNode *head=new TreeNode(pre[0]); if(pre.size()==1) return head; int i,loc=0; vector pre_left,pre_right,vin_left,vin_right; for(i=0;ileft=reConstructBinaryTree(pre_left,vin_left); head->right=reConstructBinaryTree(pre_right,vin_right); return head; }};
代码运行结果:
运行时间:3ms占用内存:484k
转载地址:https://blog.csdn.net/Jeaten/article/details/107975276 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月07日 09时18分23秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
说说如何使用 Canvas 绘制弧线与曲线
2019-04-26
系统架构设计笔记(64)—— 嵌入式系统设计
2019-04-26
系统架构设计笔记(65)—— 项目的范围、时间与成本
2019-04-26
系统架构设计笔记(66)—— 配置管理与文档管理
2019-04-26
说说 Python 元组的高级用法
2019-04-26
系统架构设计笔记(66)—— 配置管理与文档管理
2019-04-26
系统架构设计笔记(67)—— 软件需求管理
2019-04-26
系统架构设计笔记(68)—— 软件开发的质量与风险
2019-04-26
系统架构设计笔记(69)—— 人力资源管理
2019-04-26
系统架构设计笔记(70)—— 软件运行评价与过程改进
2019-04-26
系统架构设计笔记(71)—— 信息系统概述
2019-04-26
说说 Canvas 的旋转功能
2019-04-26
说说 Canvas 的缩放功能
2019-04-26
系统架构设计笔记(72)—— 信息系统工程
2019-04-26
系统架构设计笔记(73)—— 政府信息化与电子政务
2019-04-26
系统架构设计笔记(74)—— 企业信息化与电子商务
2019-04-26
系统架构设计笔记(75)—— 知识管理与商业智能
2019-04-26
说说在 log4j 中如何把日志记录到不同的文件中
2019-04-26