LeetCode C++ 105. Construct Binary Tree from Preorder and Inorder Traversal【Tree/分治】中等
发布日期:2021-07-01 02:52:15
浏览次数:2
分类:技术文章
本文共 1369 字,大约阅读时间需要 4 分钟。
Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]inorder = [9,3,15,20,7]
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 & preorder, vector & inorder) { return rebuild(0, preorder.size() - 1, 0, inorder.size() - 1, preorder, inorder); } TreeNode* rebuild(int leftpre, int rightpre, int leftin, int rightin, vector &preorder, vector &inorder) { if (leftpre > rightpre || leftin > rightin) return nullptr; TreeNode *root = new TreeNode(preorder[leftpre]); int rootin = leftin; while (rootin <= rightin && inorder[rootin] != preorder[leftpre]) ++rootin; int leftsize = rootin - leftin; root->left = rebuild(leftpre + 1, leftpre + leftsize, leftin, rootin - 1, preorder, inorder); root->right = rebuild(leftpre + leftsize + 1, rightpre, rootin + 1, rightin, preorder, inorder); return root; }};
转载地址:https://memcpy0.blog.csdn.net/article/details/108806846 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月19日 23时28分53秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
《增长黑客》(肖恩·艾利斯)学习笔记——第二部分 实战
2019-05-01
python使用HTMLTestRunner查看运行函数
2019-05-01
linux下安装jenkins+git+python
2019-05-01
解决uiautomatorviewer中添加xpath的方法
2019-05-01
性能测试的必要性评估以及评估方法
2019-05-01
Spark学习——利用Mleap部署spark pipeline模型
2019-05-01
Oracle创建表,修改表(添加列、修改列、删除列、修改表的名称以及修改列名)
2019-05-01
使用redis实现订阅功能
2019-05-01
对称加密整个过程
2019-05-01
java内存模型
2019-05-01
volatile关键字
2019-05-01
Servlet_快速入门
2019-05-01
Request_继承体系
2019-05-01
前端权限控制:获取用户信息接口构造数据
2019-05-01
七牛云存储:断点续传
2019-05-01
字节流复制文本文件【应用】
2019-05-01
私钥加密私钥解密
2019-05-01
锁的释放流程-ReentrantLock.unlock
2019-05-01
Java判断字符串是否为数字(浮点类型也包括)
2019-05-01