
Python利用前序和中序遍历结果重建二叉树的方法
本文实例讲述了Python利用前序和中序遍历结果重建二叉树的方法。分享给大家供大家参考,具体如下:
题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
这道题比较容易,前序遍历的结果中,第一个结点一定是根结点,然后在中序遍历的结果中查找这个根结点,根结点左边的就是左子树,根结点右边的就是右子树,递归构造出左、右子树即可。示意图如图所示:
利用前序和中序遍历的结果重建二叉树
Python代码:
# coding: utf-8
'''
题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
'''
class Node:
def __init__(self, data, left, right):
self.data = data
self.left = left
self.right = right
def construct_tree(pre_order, mid_order):
# 忽略参数合法性判断
if len(pre_order) == 0 :
return None
# 前序遍历的第一个结点一定是根结点
root_data = pre_order[0]
for i in range(0, len(mid_order)):
if mid_order[i] == root_data:
break
# 递归构造左子树和右子树
left = construct_tree(pre_order[1 : 1 + i], mid_order[:i])
right = construct_tree(pre_order[1 + i:], mid_order[i+1:])
return Node(root_data, left, right)
if __name__ == '__main__':
pre_order = [1, 2, 4, 7, 3, 5, 6, 8]
mid_order = [4, 7, 2, 1, 5, 3, 8, 6]
root = construct_tree(pre_order, mid_order)
print root.data
print root.left.data
print root.right.data
print root.left.left.data
print root.left.left.right.data
print root.right.right.left
print root.right.left.data
数据分析咨询请扫描二维码
若不方便扫码,搜微信号:CDAshujufenxi
SASEM 决策树:理论与实践应用 在复杂的决策场景中,如何从海量数据中提取有效信息并制定科学决策,是各界关注的焦点。SASEM 决 ...
2025-07-30SPSS 语法使用详解 在当今数据驱动的时代,SPSS( Statistical Package for the Social Sciences)作为一款功能强大的统计分析软 ...
2025-07-30人工智能对CDA数据分析领域的影响 人工智能对 CDA(Certified Data Analyst,注册数据分析师)数据分析领域的影响是全方位、多层 ...
2025-07-30MySQL执行计划中rows的计算逻辑:从原理到实践 MySQL 执行计划中 rows 的计算逻辑:从原理到实践 在 MySQL 数据库的查询优化中 ...
2025-07-29左偏态分布转正态分布:方法、原理与实践 左偏态分布转正态分布:方法、原理与实践 在统计分析、数据建模和科学研究中,正态分 ...
2025-07-29CDA 数据分析师的职业生涯规划:从入门到卓越的成长之路 在数字经济蓬勃发展的当下,数据已成为企业核心竞争力的重要来源,而 CD ...
2025-07-29CDA数据分析师证书考取全攻略 一、了解 CDA 数据分析师认证 CDA 数据分析师认证是一套科学化、专业化、国际化的人才考核标准, ...
2025-07-29解析神经网络中 Softmax 函数的核心作用 在神经网络的发展历程中,激活函数扮演着至关重要的角色,它们为网络赋予了非线性能力, ...
2025-07-29解析 response.text 与 response.content 的核心区别 在网络数据请求与处理的场景中,开发者经常需要从服务器返回的响应中提取数 ...
2025-07-29鸢尾花判别分析:机器学习中的经典实践案例 在机器学习的世界里,有一个经典的数据集如同引路明灯,为无数初学者打开了模式识别 ...
2025-07-29用 Python 开启数据分析之旅:从基础到实践的完整指南 在数据驱动决策的时代,数据分析已成为各行业不可或缺的核心能力。而 Pyt ...
2025-07-29从 CDA LEVEL II 考试题型看 Python 数据分析要点 在数据科学领域蓬勃发展的当下,CDA(Certified Data Analyst)认证成为众多从 ...
2025-07-29CDA 数据分析师的工作范围解析 在数字化时代的浪潮下,数据已成为企业发展的核心资产之一。CDA(Certified Data Analyst)数据分 ...
2025-07-29解析 insert into select 是否会锁表:原理、场景与应对策略 在数据库操作中,insert into select 是一种常用的批量数据插入语句 ...
2025-07-29用 Power BI 制作地图热力图:基于经纬度数据的实践指南 在数据可视化领域,地图热力图凭借直观呈现地理数据分布密度的优势,成 ...
2025-07-29从数据到决策:CDA 数据分析师如何重塑职场竞争力与行业价值 在数字经济席卷全球的今天,数据已从 “辅助工具” 升级为 “核心资 ...
2025-07-292025 年 CDA 数据分析师考纲焕新,引领行业人才新标准 在数字化浪潮奔涌向前的当下,数据已成为驱动各行业发展的核心要素。作为 ...
2025-07-29PyTorch 核心机制:损失函数与反向传播如何驱动模型进化 在深度学习的世界里,模型从 “一无所知” 到 “精准预测” 的蜕变,离 ...
2025-07-29t 检验与 Wilcoxon 检验:数据差异分析的两大核心方法 在数据分析的广阔领域中,判断两组或多组数据之间是否存在显著差异是一项 ...
2025-07-29PowerBI 添加索引列全攻略 在使用 PowerBI 进行数据处理与分析时,添加索引列是一项极为实用的操作技巧。索引列能为数据表中的每 ...
2025-07-29