首页 > 代码库 > [算法题] 重建二叉树
[算法题] 重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
题目思路
本题就是按照建立二叉树的思路建立就行了。先序遍历的第一个是根节点，然后在中序遍历找到该根节点，以此为界，中序遍历的左边是它的左子树的中序遍历，同样地找到该左子树在先序遍历中对应的先序遍历顺序。对于右子树也是一样的方法。
本体采用递归，递归就要先写出终止条件。
Python代码
这个题目用Python非常方便，因为可以直接利用到Python中的切片技术，省时省力通俗易懂。Java版本相对复杂得多。
# -*- 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 len(pre)==0 or len(tin)==0: return if len(pre)==1: return TreeNode(pre[0]) node=TreeNode(pre[0]) for i in range(len(tin)): if tin[i]==pre[0]: break node.left=self.reConstructBinaryTree(pre[1:i+1],tin[:i]) node.right=self.reConstructBinaryTree(pre[i+1:],tin[i+1:]) return node
[算法题] 重建二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。