牛客网在线编程之重建二叉树

为了练习编程，每日签到！！！

小白一枚，刚开始练习，顺便练习python

题目描述

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

思路

题目给出了先序遍历和中序遍历，通过演算可得出以下规律，先序遍历优先遍历二叉树的根节点，因此可以将先序遍历的顺序作为建二叉树的基础，而中序遍历则决定了两节点的子树关系。从先序遍历的初始节点开始推算，第一个节点肯定是根节点，从第二个节点开始，依次与根节点形成节点对，带入中序遍历的数组中进行判断并创建子树，在中序遍历中，判断创建节点与根节点的位置关系，在根节点左边则说明该节点是根节点的左子树，否则是右子树。然后就是递归操作，判断根节点的左右子树是否为空，不为空则根据前面的判断，将创建的新节点赋为根节点子树。

伪代码

def createTree(root,child):
if root.中序序列>child.中序：
    #左子树
    if root.left==None:
        root.left=child
    else:
        createTree(root.left,child)#递归
if root.中序序列<child.中序：
    #右子树
    if root.right==None:
        root.right=child
    else:
        createTree(root.right,child)#递归

附录

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:

    def creatTree(self,root,child,post_order):
        if post_order.index(root.val)>post_order.index(child.val):
            if root.left==None:
                root.left=child
            else:
                self.creatTree(root.left,child,post_order)
        else:
            if root.right==None:
                root.right=child
            else:
                self.creatTree(root.right,child,post_order)

    def listTree(self,root,key=None):
        if(key==0):
            print(root.val,end=)
            if root.left!=None:
                self.listTree(root.left,0)
            if root.right!=None:
                self.listTree(root.right,0)
        if(key==1):
            if root.left!=None:
                self.listTree(root.left,1)
            print(root.val,end=)
            if root.right!=None:
                self.listTree(root.right,1)
        if(key==2):
            if root.left!=None:
                self.listTree(root.left,2)
            if root.right!=None:
                self.listTree(root.right,2)
            print(root.val,end=)
    def reConstructBinaryTree(self,pre,tin):
        root=TreeNode(pre[0])
        i=0
        while i+1<len(pre):
            child=TreeNode(pre[i+1])
            #print(root)
            self.creatTree(root,child,tin)
            i+=1
        return root

if __name__=="__main__":
    pre_order = [1,2,4,7,3,5,6,8]
    post_order= [4,7,2,1,5,3,8,6]
    #print(pre_order.index(4))
    
    a=Solution()
    root=a.reConstructBinaryTree(pre_order,post_order)
    #print(root)
    a.listTree(root,1)