R语言 UI Automator VR全景图片 细胞因子 开源商城系统 ssh命令 SCI authentication routes grunt Egret Engine bootstrap后台管理模板 jquery使用ajax jq解析json python转16进制 jquery关闭当前窗口 mysql批量更新数据 vue使用bootstrap svn查看历史版本 range函数python react python环境搭建 python正则表达式例子 python链接mysql数据库 python获取字典的值 简单python脚本实例 python匹配字符串 python写入txt文件 java使用 java运算 java泛型方法 灼热峡谷 redis入门指南 一键换系统 电脑必备软件排行榜 crazytalk 路由器有没有辐射 rar去广告 idea重命名快捷键 华为交换机学习指南
当前位置: 首页 > 学习教程  > 编程语言

从前序与中序遍历序列构造二叉树-LeetCode

2021/1/28 23:24:32 文章标签:

题目: 题目链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/ 思路: 题目给定的无重复元素是关键,否则无法根据前序在中序里找到每个子树的根节点规律就是前序的每…

题目:

在这里插入图片描述

题目链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/

思路:

  1. 题目给定的无重复元素是关键,否则无法根据前序在中序里找到每个子树的根节点
  2. 规律就是前序的每个子序列的第一个元素,在中序里都能够将中序切为它自己的左右子树
  3. 比如题目给定的3,将中序划分为 [9]、[15,20,7],9即为3的左子树的根结点,前序剩余的[20,15,7]的20又是3的右子树的根结点,且可以将剩余中序划分为[15]、[7]两个子序列
  4. 递归上述步骤,减少问题规模,重建左右子树并返回,终止条件就是左右子序列都没有值了

代码:

# 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]) -> TreeNode:
        if not preorder or not inorder: return None
        root = TreeNode(preorder[0])
        i = inorder.index(root.val)

        # 递归重建左右子树,注意切片区间左闭右开
        root.left = self.buildTree(preorder[1:i+1],inorder[:i])
        root.right = self.buildTree(preorder[i+1:],inorder[i+1:])
        return root;

本文链接: http://www.dtmao.cc/news_show_650200.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?