# python实现代码_重建二叉树

XAMPP案例 907浏览

## 题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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 = None
class Solution:
def reConstructBinaryTree(self, pre, tin):
if  pre==[]:
return None
root = TreeNode(pre[0]) # 取出前序序列的第一个元素为根节点元素
root_index = tin.index(pre[0])  #  根节点pre[0]在中序序列中的索引为root_index
root.left = self.reConstructBinaryTree(pre[1:root_index+1], tin[:root_index])
root.right = self.reConstructBinaryTree(pre[root_index+1:], tin[root_index+1:])
return root
``````

`测试：`

``s=Solution()``Tree=s.reConstructBinaryTree([1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6])``print(Tree)``# result：``

# <__main__.TreeNode object at 0x000001A4A8BCE898>

``# 前序遍历（DLR）``def DLR(root):``    if root == None:``        return []``    m=root.val``    left=DLR(root.left)``    right=DLR(root.right)``    return [m]+left+right``# 中序遍历（LDR）``def LDR(root):``    if root == None:``        return []``    m=root.val``    left=LDR(root.left)``    right=LDR(root.right)``    return left+[m]+right``# 后序遍历（LRD）``def LRD(root):``    if root == None:``        return []``    m=root.val``    left=LRD(root.left)``    right=LRD(root.right)``    return left+right+[m]``print("前序遍历",DLR(Tree))``print("中序遍历",LDR(Tree))``print("后序遍历",LRD(Tree))``# result:``前序遍历 [1, 2, 4, 7, 3, 5, 6, 8]``中序遍历 [4, 7, 2, 1, 5, 3, 8, 6]``后序遍历 [7, 4, 2, 5, 8, 6, 3, 1]``

``# -*- coding:utf-8 -*-``class TreeNode:``    def __init__(self, x):``        self.val = x``        self.left = None``        self.right = None``class Solution:``    def reConstructBinaryTree(self, back, tin):``        if  back==[]:``            return None``        root = TreeNode(back[-1]) # 取出后序序列的最后一个元素back[-1]为根节点元素``        root_index = tin.index(back[-1])  #  根节点在中序序列的索引为root_index ``        root.left = self.reConstructBinaryTree(back[0:root_index], tin[:root_index])``        root.right = self.reConstructBinaryTree(back[root_index:-1], tin[root_index+1:])``        return root``

``# -*- coding:utf-8 -*-``class TreeNode:``    def __init__(self, x):``        self.val = x``        self.left = None``        self.right = None``class Solution:``    def reConstructBinaryTree(self, pre, tin):``        if  pre==[]:``            return None``        root = TreeNode(pre[0]) # 取出前序序列的第一个元素为根节点元素``        root_index = tin.index(pre[0])  #  根节点pre[0]在中序序列中的索引为root_index ``        root.left = self.reConstructBinaryTree(pre[1:root_index+1], tin[:root_index])``        root.right = self.reConstructBinaryTree(pre[root_index+1:], tin[root_index+1:])``        return root``