首页 > 试题广场 >

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

[编程题]从中序与后序遍历序列构造二叉树
  • 热度指数：9176 时间限制：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，点此查看相关信息
算法知识视频讲解
开通博客
头像 fred-coder
发表于 2021-12-04 20:21:05
中序遍历: 左 -> 根 -> 又 后序遍历: 左 -> 右 -> 根 则后序遍历的最后一个节点为根节点,该节点在中序数组中的索引 idx 的左侧即为左子树[0:idx],右侧为右子树 [idx + 1:]，该索引代表了左子树的长度,在后序数组中左子树为[0:idx],右子树 展开全文
去ta的博客 赞 (12) 回复(1) 收起
头像 空中转体一周半
发表于 2022-05-22 08:58:23
这个题的思路是和根据中前遍历重建二叉树类似的。因为后续遍历的最后一个元素总是根节点，那么只需要先找到后序遍历中的根节点，再把数组分为左右两个区间就能找到左子树与右子树。 public class Solution { public TreeNode buildTree (int[] inor 展开全文
去ta的博客 赞 (11) 回复(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的博客 赞 (5) 回复(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) 回复(2) 收起
头像 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的博客 赞 (3) 回复(0) 收起
头像 Mr.galaxy
发表于 2022-11-11 23:06:11
c++取vector子串比较麻烦 具体可参考网址：C++容器vector的数组片段截取操作_stitching的博客-CSDN博客_vector截取一部分 如果个人感觉两个数组遍历一遍即可出答案，奈何才疏学浅，想不出来，如果大家有更好的方法还请大家分享出来！ /**  *& 展开全文
去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) 收起
头像 17c89
发表于 2024-11-30 17:11:20
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int v 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 fikry102
发表于 2025-05-02 00:56:15
分治法：将原问题分解成若干个规模较小的子问题，这些子问题的结构与原问题相似。通常，子问题是相互独立的，并且问题规模通常比原问题小。 # class TreeNode: # def __init__(self, x): # self.val = x # self 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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