剑指Offer[Python版]
2021-02-12 23:19
标签：思路 inter www 重复 考题 返回 代码 self offer 面试题6 重建二叉树 参考题目地址：剑指Offer编程题 牛客网 剑指Offer[Python版] 标签：思路 inter www 重复 考题 返回 代码 self offer 原文地址：https://www.cnblogs.com/eugene0/p/12729114.html
题目表述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解题思路：
递归思想。前序遍历中第一个元素是根，因此在中序遍历中找到根的位置下标，根将中序遍历分为两部分，分别是左子树和右子树，然后继续递归寻找左右子树的根节点。
代码：class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if not pre or not tin:
return None
root = TreeNode(pre[0])
index = tin.index(pre[0])
root.left = self.reConstructBinaryTree(pre[1:1+index],tin[:index])
root.right = self.reConstructBinaryTree(pre[1+index:],tin[1+index:])
return root
上一篇：[.net 面向对象编程基础] (16) 数组与集合
下一篇：回顾：螺旋打印数组