最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

python实现代码_重建二叉树

XAMPP案例 admin 50浏览 0评论

重建二叉树

题目描述:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

思路:前序遍历序列的第一个元素是根节点的值,根据这个值找到中序遍历序列中的根节点元素的索引,此时根据中序遍历序列的根节点元素的左侧和右侧分别为左子树和右子树的元素。本例中,前序序列[1,2,4,7,3,5,6,8],根节点元素为1,中序序列[4,7,2, 1,  5,3,8,6]可得左子树元素为[4,7,2],右子树元素为[5,3,8,6]。由此可知左子树的中序遍历为[4,7,2],在原前序序列中有[2,4,7],因此该子树的根节点元素为2,依次推断出二叉树的结构如下:

BA85

在根节点确定后,左子树的前序和中序序列可在原前序和中序序列里通过下标索引取得,同理,右子树也是如此,对左右子树进行递归操作,最终可重建该二叉树。

 


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

 

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

 

转载请注明:XAMPP中文组官网 » python实现代码_重建二叉树