剑指offer:重建二叉树(Python)
程序员文章站
2022-06-17 18:27:03
...
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
思路:
算法设计思想
前序遍历序列的第一个元素为根结点的值,然后在中序遍历序列中寻找根节点的值的位置(索引)。
从中序遍历序列的起始位置到根结点的值的位置(不包含)为根结点左子树的中序遍历序列;从中序遍历序列的根结点的值的位置(不包含)到结束位置为根结点右子树的中序遍历序列;相应的,从前序遍历序列的第二个元素开始的根结点左子树结点数个元素的子序列为根结点左子树的前序遍历序列,从下一个元素开始,直到结束位置的子序列为根结点右子树的前序遍历序列。如图 2.7 所示,
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if len(pre)==0:
return None
if len(pre)==1:
return TreeNode(pre[0])
else:
res = TreeNode(pre[0])
res.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[:tin.index(pre[0])])
res.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:])
return res
另外:Python List index()方法
index() 函数用于从列表中找出某个值第一个匹配项的索引位置。
推荐阅读
-
《剑指offer》面试题6 重建二叉树
-
剑指offer25:复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),结果返回复制后复杂链表的head。
-
剑指offer31:整数中1出现的次数(从1到n整数中1出现的次数)
-
剑指offer28:找出数组中超过一半的数字。
-
剑指offer27:按字典序打印出该字符串中字符的所有排列
-
C#版剑指Offer-001二维数组中的查找
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
剑指offer13:数组[奇数,偶数],奇数偶数相对位置不变。
-
Python利用前序和中序遍历结果重建二叉树的方法
-
剑指offer第二天