首页 > 其他分享 >【代码随想录】刷题记录(55)-从中序与后序遍历序列构造二叉树

【代码随想录】刷题记录(55)-从中序与后序遍历序列构造二叉树

时间:2024-12-03 14:57:54浏览次数:9  
标签:right 55 root self 随想录 二叉树 left inorder postorder

题目描述:

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

 

示例 1:

 

3191074cd189469c9d9199a126b6d035.jpeg

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]

示例 2:

输入:inorder = [-1], postorder = [-1]
输出:[-1]

 

提示:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder 和 postorder 都由 不同 的值组成
  • postorder 中每一个值都在 inorder 中
  • inorder 保证是树的中序遍历
  • postorder 保证是树的后序遍历

 

我的作答:

下午写得好困好困好困好困。。。思路如下:

7f4367712dd04d7fa3a1bdd84ad6bc80.png

后序的最后一个元素一定是根结点,通过根节点的值比对中序,找到切割的下标index,再递归分解左子树和右子树;

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: Optional[TreeNode]
        """
        if not postorder: #后序数组为空
            return None
        rootvalue = postorder[-1] #根节点的值
        root = TreeNode(rootvalue)
        if len(postorder)==1: #剪枝,如果后序数组只有根节点
            return root
        for index in range(len(inorder)):
            if inorder[index]==rootvalue: #找到中结点的下标
                break
        root.left = self.buildTree(inorder[0:index], postorder[0:index])
        root.right = self.buildTree(inorder[index+1:len(inorder)], postorder[index:len(postorder)-1])
        return root

5147ab0e2da34fdd9a79fb640725edc6.png

 

参考代码:差不多

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: Optional[TreeNode]
        """
        if not postorder:
            return None

        # 第二步: 后序遍历的最后一个就是当前的中间节点.
        root_val = postorder[-1]
        root = TreeNode(root_val)

        # 第三步: 找切割点.
        separator_idx = inorder.index(root_val)

        # 第四步: 切割inorder数组. 得到inorder数组的左,右半边.
        inorder_left = inorder[:separator_idx]
        inorder_right = inorder[separator_idx + 1:]

        # 第五步: 切割postorder数组. 得到postorder数组的左,右半边.
        # ⭐️ 重点1: 中序数组大小一定跟后序数组大小是相同的.
        postorder_left = postorder[:len(inorder_left)]
        postorder_right = postorder[len(inorder_left): len(postorder) - 1]

        # 第六步: 递归
        root.left = self.buildTree(inorder_left, postorder_left)
        root.right = self.buildTree(inorder_right, postorder_right)
         # 第七步: 返回答案
        return root

d7e5c3e828ee40d799435608af6877dc.png

 

标签:right,55,root,self,随想录,二叉树,left,inorder,postorder
From: https://blog.csdn.net/Aerochacha/article/details/144214830

相关文章

  • cmu15545笔记-并发控制总结(Concurrency Control Summary)
    目录总览ACID串行化与冲突操作隔离级别概念层级二阶段锁原理级联回滚强二阶段锁死锁检测和避免锁层级实践应用实现的隔离级别OOC原理三个阶段实现的隔离级别处理幻读MVC原理写偏差异常(WriteSkewAnomaly)版本存储(Version-storage)AppendOnlyTimeTravelStorageDeltaStorage垃圾......
  • 代码随想录-数组2
    977.有序数组的平方力扣题目链接基本思路暴力解法,先全部平方,然后排序双指针法,由于原本数组是有序的,从负数到正数,平方之后最大数只会出现在两端的位置。考虑设置一个新数组存放排序后的元素,利用相向指针判断选择要把哪个元素先放入新数组。暴力排序classSolution{pu......
  • 236.二叉树的最近公共祖先
    题目:给定一个二叉树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树T的两个节点p、q,最近公共祖先表示为一个节点x,满足x是p、q的祖先且x的深度尽可能大(一个节点也可以是它自己的祖先)。”示例1:输入:root=[3,5,1,6,2,0,8,......
  • 代码随想录算法训练营第三十一天|leetcode56. 合并区间、leetcode738.单调递增的数字
    1leetcode56.合并区间题目链接:56.合并区间-力扣(LeetCode)文章链接:代码随想录视频链接:贪心算法,合并区间有细节!LeetCode:56.合并区间哔哩哔哩bilibili思路:其实很清楚,跟之前的方法差不多,但是自己写的时候就是有地方不会了,会不知道接下来的思路是什么1.1视频后的思路卡壳......
  • springboot企业合同管理系统-计算机毕业设计源码45527
    目 录摘要1绪论1.1研究背景1.2 研究意义1.3论文结构与章节安排2 企业合同管理系统的设计与实现系统分析2.1可行性分析2.2系统流程分析2.2.1数据增加流程2.2.2数据修改流程2.2.3数据删除流程2.3 系统功能分析2.3.1功能性分析2.4 系统......
  • 博主自留二叉树万字长文—>涵盖名词辨析 + 树的两种表示方法 + 所有特殊二叉树 + 图解
    玩转二叉树(概念+图解+例题代码详解)一、树的概念我们知道在计算机什么是树吗?是二月春风似剪刀吗?哈哈哈哈哈哈显然不是我们看下面这张图,可以观察到树的一些特征1、树的特征(1)树是非线性的数据结构,是递归定义的(连通性)(2)子树之间不能有任何交集(无环性)(3)一颗N......
  • 二叉树の节点x的双亲节点
    算法思想:通过一个栈来辅助非递归地遍历二叉树。先向左遍历二叉树,将经过的节点依次入栈,并标记其tag为0(表示左孩子未遍历完),直到找到目标节点或者左子树为空。若找到目标节点,就输出栈顶节点的数据作为父节点并返回。若未找到且栈顶节点的右子树已遍历(tag为1),则弹出栈顶节点。若栈......
  • 数据结构(7)—二叉树_堆专题
    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录前言一、二叉树概念二、堆的插入与删除1.插入-Up向上调整2.删除-Down向下调整堆排序前言堆(Heap)是一种特殊的树形数据结构,通常用于实现优先队列。堆可以是二叉堆,也可以推广到k元堆,但最常见......
  • 完全二叉树的应用--堆
    目录1.堆的概念2.性质3.逻辑结构和物理结构(存储结构)4.堆的实现前提5.堆的实现思考:插入数据之前,得保证之前的数据是一个堆。为什么要这样?思考:为什么先改变child的值,先改parent的值不可以么? 5.2向下调整建堆思考:为什么先动parent,后动child?1.堆的概念如果有一个......
  • 代码随想录算法训练营第十四天 | 226.翻转二叉树、 101. 对称二叉树、104.二叉树的最
    文档讲解:代码随想录视频讲解:代码随想录状态:完成4道题226.翻转二叉树整体思路:交换每一个节点的左右孩子思考:使用哪种遍历方式?建议使用前序或后序遍历(中序遍历比较绕)​前序遍历#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,va......