首页 > 试题广场 >

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

[编程题]从中序与后序遍历序列构造二叉树
  • 热度指数：5529 时间限制：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，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
Python3
在找内推的祖国花朵很洒脱头像 在找内推的祖国花朵很洒脱
class Solution:
    def buildTree(self , inorder: List[int], postorder: List[int]) -> TreeNode:
        def build(pos_left, pos_right, mid_left, mid_right):
            if pos_left > pos_right or mid_left > mid_right:  # 停止条件
                return None
            root = TreeNode(postorder[pos_right])  # 构建节点
            mid_root = mid_left
            while mid_root <= mid_right and inorder[mid_root] != postorder[pos_right]:  #找寻根节点
                mid_root += 1
            diff = mid_root - mid_left  # 左子树的长度
            root.left = build(pos_left, pos_left + diff -1, mid_left, mid_root - 1)  # 构建左子树
            root.right = build(pos_left + diff, pos_right - 1, mid_root + 1, mid_right)  # 构建右子树
            return root  # 返回构建好的树

        return build(0, len(postorder) - 1, 0, len(inorder) - 1)

发表于 2023-07-21 12:59:02 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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