python实现代码_重建二叉树

# -*- 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>

输出的是该树节点存放的地址。

下面我们来通过三种不同的方式遍历上述已经重建的二叉树，其中有根结点D、左子树L、右子树R。

# 前序遍历（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]

可见遍历结果与题目中给定的一致。

【拓展：已知前序遍历和中序遍历的组合，中序遍历和后序遍历的组合均可以逆向推断出唯一的二叉树，而已知前序和后序遍历的组合不能逆向推断出唯一的二叉树】。

以下通过后序遍历序列(back)和中序遍历序列(tin)的组合对二叉树进行重建，关键点：后续遍历序列的最后一个元素为根节点元素。

# -*- coding:utf-8 -*-class TreeNode:    def __init__(self, x):        self.val = x        self.left = None        self.right = Noneclass 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