剑指offer-python刷题-重建二叉树
发布日期:2021-07-28 12:03:18
浏览次数:4
分类:技术文章
本文共 705 字,大约阅读时间需要 2 分钟。
题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
二叉树前序遍历的第一个结点一定是根节点,根据根节点在后序遍历中的位置,可以获得该二叉树根节点的左子树和右子树的前序遍历和中序遍历,由此可以调用递归算法。
# -*- coding:utf-8 -*-# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: # 返回构造的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): # write code here if not pre: return None root = TreeNode(pre[0]) m = tin.index(pre[0]) root.left = self.reConstructBinaryTree(pre[1:1+m],tin[0:m]) root.right = self.reConstructBinaryTree(pre[m+1:],tin[m+1:]) return root
转载地址:https://blog.csdn.net/sinat_42437278/article/details/118250529 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月09日 16时35分33秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【大话Mysql面试】-Mysql事务以及隔离级别
2019-04-26
【大话Mysql面试】-Mysql索引
2019-04-26
【大话Mysql面试】-Mysql锁
2019-04-26
【大话Mysql面试】-Mysql常见面试题目
2019-04-26
08 【多线程高并发】Java线程间通信的方式
2019-04-26
【数据结构与算法】什么是跳表?通俗易懂来理解跳表
2019-04-26
【数据结构与算法】什么是图?图是什么?快速带你回顾图有关的知识点
2019-04-26
【数据结构与算法】什么是串?什么是KMP算法?字符串匹配是什么?
2019-04-26
【数据结构与算法】什么是布隆过滤器?如何防止缓存穿透的问题?
2019-04-26
【面试题目】Java设计模式你有哪些了解?说几个常用的。
2019-04-26
【计算机操作系统】常说的死锁是什么?死锁产生的必要条件是什么?死锁的解决策略是什么?
2019-04-26
【计算机操作系统】设备管理?磁盘结构是怎么样的?磁盘调度算法有哪些?
2019-04-26
【多线程高并发】为什么要使用多线程?创建多少个线程合适呢?
2019-04-26
【多线程与高并发】 Java两个线程轮流打印1-100两个数?多线程轮流打印数字?
2019-04-26
【多线程与高并发】 Java两个线程轮流打印字符串?
2019-04-26
【Linux命令篇】Linux命令实践
2019-04-26
【Leetcode单调队列】Leetcode239 滑动窗口最大值
2019-04-26