首页 > 试题广场 >

从中序与后序遍历序列构造二叉树

[编程题]从中序与后序遍历序列构造二叉树
  • 热度指数：5591 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树的中序与后序遍历结果，请你根据两个序列构造符合这两个序列的二叉树。

数据范围：二叉树的节点数满足 ，节点上的值满足 ，保证节点的值各不相同

例如输入[2,1,4,3,5],[2,4,5,3,1]时，
根据中序遍历的结果[2,1,4,3,5]和后序遍历的结果[2,4,5,3,1]可构造出二叉树{1,2,3,#,#,4,5}，如下图所示：

示例1

输入

[1],[1]

输出

{1}
示例2

输入

[2,1,4,3,5],[2,4,5,3,1]

输出

{1,2,3,#,#,4,5}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
开通博客
头像 空中转体一周半
发表于 2022-05-22 08:58:23
这个题的思路是和根据中前遍历重建二叉树类似的。因为后续遍历的最后一个元素总是根节点，那么只需要先找到后序遍历中的根节点，再把数组分为左右两个区间就能找到左子树与右子树。 public class Solution { public TreeNode buildTree (int[] inor 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 fred-coder
发表于 2021-12-04 20:21:05
中序遍历: 左 -> 根 -> 又 后序遍历: 左 -> 右 -> 根 则后序遍历的最后一个节点为根节点,该节点在中序数组中的索引 idx 的左侧即为左子树[0:idx],右侧为右子树 [idx + 1:]，该索引代表了左子树的长度,在后序数组中左子树为[0:idx],右子树 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 加油做题
发表于 2022-06-13 19:41:47
struct TreeNode* buildTree(int* inorder, int inorderLen, int* postorder, int postorderLen ) { // write code here if(inorderLen==0){ re 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 你说夕阳很美
发表于 2022-01-11 16:29:52
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) { 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 Mr.galaxy
发表于 2022-11-11 23:06:11
c++取vector子串比较麻烦 具体可参考网址：C++容器vector的数组片段截取操作_stitching的博客-CSDN博客_vector截取一部分 如果个人感觉两个数组遍历一遍即可出答案，奈何才疏学浅，想不出来，如果大家有更好的方法还请大家分享出来！ /**  *& 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Coming680
发表于 2022-03-19 09:58:13
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) { 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 landf31
发表于 2022-04-10 10:42:53
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int v 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客270908258号
发表于 2022-02-02 19:44:28
思路： 1.中序遍历顺序:左根右；后序遍历顺序：左右根；根据给出的后序遍历数组可知，数组末元素为根结点值；取出该结点，作为根结点的值。 2.根据中序遍历顺序，找出根结点位置rootIdx；在中序遍历数组中，该结点左边元素为左子树结点值，右边为右子树结点值；在后序遍历数组中，可知从0到rootIdx为 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 酸甜苦辣复何求
发表于 2023-03-27 16:22:23
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */这不是我自己写出来的，看了别人的方法，然后理解 了 /** * 代码中的类名、方法名、参数名已经指定 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 咸鱼跃龙门
发表于 2023-08-02 11:01:16
class Solution { public: TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& postorder) { return helper(i 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

数组 分治 树 哈希 递归
难度：
21条回答 3591浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号