LeetCode105之从前序与中序遍历序列构造二叉树(相关话题:前序中序遍历二叉树)
2023-09-11 14:20:00 时间
题目描述
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均无重复元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列
解题思路
对于任意一颗树而言,前序遍历的形式总是
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
只要我们在中序遍历中定位到根节点,那么我们就可
相关文章
- Java实现 LeetCode 105 从前序与中序遍历序列构造二叉树
- Java实现 蓝桥杯VIP 算法提高 最长公共子序列
- Lintcode--010(最长上升子序列)
- LeetCode(106):从中序与后序遍历序列构造二叉树
- 【原创】MySQL Proxy - query注入动作中的脚本序列
- LeetCode(106):从中序与后序遍历序列构造二叉树
- leetcode 105. 从前序与中序遍历序列构造二叉树
- ML之prophet:利用prophet算法对维基百科页面的日志每日页面浏览量实现回归预测(时间序列的趋势/周季节性趋势/年季节性趋势)案例
- 516. 最长回文子序列-动态规划算法
- 105. 从前序与中序遍历序列构造二叉树
- 106. 从中序与后序遍历序列构造二叉树
- 解答私信@YWang521 //C++ 编写程序,计算序列 1-2/3+3/5-4/7+5/9-6/11+...+(-1)^(n-1)/(2n-1)的前n项之和
- 【数字信号处理】序列傅里叶变换 ( 序列傅里叶变换定义详细分析 | 证明单位复指数序列正交完备性 | 序列存在傅里叶变换的性质 | 序列绝对可和 → 序列傅里叶变换一定存在 )
- 九度 称号1377:缓变序列
- Linux基础命令-seq打印数字序列
- 状态机-重叠序列检测
- 【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列
- Python enumerate() 函数【将可遍历的数据对象(如列表、元组或字符串)变为一个索引序列】
- 07 串行数据流特定序列循环检测器的设计与功能验证(附源码)