【代码随想录day19】从前序与中序遍历序列构造二叉树

这篇具有很好参考价值的文章主要介绍了【代码随想录day19】从前序与中序遍历序列构造二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目 

【代码随想录day19】从前序与中序遍历序列构造二叉树,代码随想录,数据结构,LeetCode,python,开发语言,leetcode,算法

 思路

使用递归建树,流程如下:

  1. 取出后序节点创建新树的节点

  2. 找到新树的节点在中序中的索引

  3. 分割中序序列

  4. 分割后序序列

  5. 继续递归建立整颗新树文章来源地址https://www.toymoban.com/news/detail-606215.html

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # 如果所有节点都已经扫过,说明新的树已经建成了,应返回空节点
        if not inorder:
            return None
        # 1.取出前序节点创建新树的节点
        root = TreeNode(preorder[0])
        
        # 2.找到新树的节点在中序中的索引
        in_index = inorder.index(root.val)
        
        # 3.分割中序序列
        in_left = inorder[:in_index]
        in_right = inorder[in_index+1:]

        # 4.分割前序序列
        pre_left = preorder[1:len(in_left)+1]
        pre_right = preorder[len(in_left)+1:]

        # 5.继续递归建立整颗新树
        root.left = self.buildTree(pre_left, in_left)
        root.right = self.buildTree(pre_right, in_right)
        return root

到了这里,关于【代码随想录day19】从前序与中序遍历序列构造二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录Day4:24. 两两交换链表中的节点,19.删除链表的倒数第N个节点 ,面试题 02.07. 链表相交 ,142.环形链表II

    题目要求:  使用虚拟头节点,代码实现: 题目要求: 我的思路: 先通过while语句找出整体链表的size,再算出要删除结点前一个结点的索引。 更简单(更妙)的方法:快慢指针法 代码实现: 题目要求: 看到题目自己首先的想法就是暴力搜索,但是会做很多不必要的遍历。

    2024年02月20日
    浏览(40)
  • 代码随想录Day58

    昨天因为志愿活动和笔试耽误了一整天,今天继续学习动规解决子序列问题。 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,\\\"ace\\\"是\\\"abcde\\\"的一个子序列,

    2023年04月27日
    浏览(52)
  • 代码随想录day44

    完全背包 其实就是每个物品可以使用无数次,给我们一个容器,装满这个容器的最大价值是多少。 思路: 如果求组合数就是外层for循环遍历物品,内层for遍历背包。 如果求排列数就是外层for遍历背包,内层for循环遍历物品。 完全背包的组合和排序 518. 零钱兑换 II 题目 给你

    2023年04月17日
    浏览(62)
  • 代码随想录day59

    647. 回文子串 给你一个字符串  s  ,请你统计并返回这个字符串中  回文子串  的数目。 回文字符串  是正着读和倒过来读一样的字符串。 子字符串  是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不

    2024年02月07日
    浏览(45)
  • 代码随想录day02

    ● 力扣题目链接 ● 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 思路 ● 暴力排序,时间复杂度O(n + nlogn) ● 使用双指针,时间复杂度O(n) 代码 ● 力扣题目链接 ● 给定一个含有 n 个正整数的数组和一个正整

    2024年02月13日
    浏览(49)
  • 代码随想录Day62

    今天继续学习单调栈解决相关问题。 nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。 给你两个 没有重复元素 的数组 nums1 和 nums2 ,下标从 0 开始计数,其中nums1 是 nums2 的子集。 对于每个 0 = i nums1.length ,找出满足 nums1

    2024年02月01日
    浏览(54)
  • 代码随想录day11

    20. 有效的括号   思路:这里用模拟栈的方法会更好理解,也就是我们每次遇到朝左方向的三种类型的时候,就加入相反方向的右括号到result栈中。由于栈是一个先进后出的方式,所以我们会有一个判断stack当前为不为空,和stack[-1]是不是和当前循环到的括号相同。如果说相同

    2024年02月13日
    浏览(43)
  • 代码随想录day01

    ● 思维不难,主要是考察对代码的掌控能力 ● 内存中的存储方式:存放在连续内存空间上的相同类型数据的集合 ● 数组可以通过下标索引获取到下标对应的数据 ● 数组下标从0开始 ● 因为内存空间地址连续,因此删除或增加元素的时候,难免移动其他元素地址 ● Java中的

    2024年02月13日
    浏览(53)
  • 代码随想录Day50

    昨天因为准备面试所以咕咕了一天。今天继续学习动规算法,尽管背包问题已经结束但其中的各类思想仍需要进一步理解。 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两

    2023年04月14日
    浏览(52)
  • 代码随想录day6

    一开始想着构建两个hash表,但如果后面字符串长的可能会超时 这里借用数组构建hash表,主要思想是26个字母组成的数组统计出现次数 如果有出现次数为非0,则说明有问题,可以加以利用作为判断条件 这里对乱序的子字符串先排序,排序后的结果是否一致可以作为分组的依

    2024年02月04日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包