LeetCode C++ 106. Construct Binary Tree from Inorder and Postorder Traversal【Tree/分治】中等
发布日期:2021-07-01 02:52:16
浏览次数:4
分类:技术文章
本文共 1498 字,大约阅读时间需要 4 分钟。
Given inorder and postorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
For example, given
inorder = [9,3,15,20,7]postorder = [9,15,7,20,3]
Return the following binary tree:
3 / \ 9 20 / \ 15 7
题意:根据一棵树的中序遍历与后序遍历构造二叉树。可以假设树中没有重复的元素。
思路
简单的分治题目,递归解决。代码如下:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution { public: TreeNode* buildTree(vector & inorder, vector & postorder) { return rebuild(0, inorder.size() - 1, 0, postorder.size() - 1, inorder, postorder); } TreeNode* rebuild(int leftin, int rightin, int leftpost, int rightpost, vector & inorder, vector & postorder) { if (leftin > rightin || leftpost > rightpost) return nullptr; TreeNode *root = new TreeNode(postorder[rightpost]); int rootin = leftin; while (rootin <= rightin && inorder[rootin] != postorder[rightpost]) ++rootin; int leftsize = rootin - leftin; root->left = rebuild(leftin, rootin - 1, leftpost, leftpost + leftsize - 1, inorder, postorder); root->right = rebuild(rootin + 1, rightin, leftpost + leftsize, rightpost - 1, inorder, postorder); return root; }};
效率如下:
执行用时:52 ms, 在所有 C++ 提交中击败了26.98% 的用户内存消耗:16.9 MB, 在所有 C++ 提交中击败了85.71% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108806945 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月14日 13时26分09秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
ELK部署搭建
2019-05-02
kafka安装与配置
2019-05-02
MHA向send_report传递的参数
2019-05-02
MySQL binlog格式解析
2019-05-02
运维监控系统之Open-Falcon
2019-05-02
数据库对比:选择MariaDB还是MySQL?
2019-05-02
名词解释:Linux内存管理之RSS和VSZ
2019-05-02
547. 省份数量
2019-05-02
基类与子类
2019-05-02
遍历操作模板
2019-05-02
固定长度与非固定长度字符串选择
2019-05-02
特殊字符转义
2019-05-02
2013年,我在培训机构学Java
2019-05-02
面试:SpringBoot中的条件注解底层是如何实现的?
2019-05-02
数据库里账号的密码,怎样存放更加安全?
2019-05-02
史上最强攻略!速度领取华为云服务器
2019-05-02
为什么阿里P8、P9技术大牛反复强调“结构化思维”?
2019-05-02
国外程序员用的火热的Vavr是什么鬼?让函数式编程更简单!
2019-05-02
5万字的《Java面试手册》V1.0版本,高清PDF免费获取
2019-05-02
缓存穿透、缓存并发、热点缓存之最佳招式
2019-05-02