題目描述

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

基本思想

前序遍歷：根節(jié)點(diǎn)->左子樹->右子樹
中序遍歷：左子樹->根節(jié)點(diǎn)->右子樹
后序遍歷：左子樹->右子樹->根節(jié)點(diǎn)

按照遍歷規(guī)則，前序遍歷序列的第一個(gè)節(jié)點(diǎn){1}一定是根節(jié)點(diǎn)，它將中序遍歷序列分為了左子樹上的節(jié)點(diǎn){4,7,2}和右子樹上的節(jié)點(diǎn){5,3,8,6}。再分析子樹{4,7,2}，它在中序遍歷里的順序{2,4,7}，說明根節(jié)點(diǎn)是{2}，左子樹{4,7}，右子樹為空。再分析子樹{4,7}，它在中序遍歷里的順序?yàn)閧4,7}，說明根節(jié)點(diǎn)是{4}，左子樹為空，右子樹為{7}，……，以此類推。

Python

# -*- coding:utf-8 -*-

# class TreeNode:

#? ? def __init__(self, x):

#? ? ? ? self.val = x

#? ? ? ? self.left = None

#? ? ? ? self.right = None

class Solution:

? ? # 返回構(gòu)造的TreeNode根節(jié)點(diǎn)

? ? def reConstructBinaryTree(self, pre, tin):

? ? ? ? # write code here

? ? ? ? if not pre or not tin:

? ? ? ? ? ? return None

? ? ? ? root? = TreeNode(pre[0]) #1 2 4 7 3 5 6 8

? ? ? ? index = tin.index(pre[0])

? ? ? ? root.left = self.reConstructBinaryTree( pre[1:index+1] , tin[:index])

? ? ? ? root.right = self.reConstructBinaryTree( pre[index+1:] , tin[index+1:])

? ? ? ? return root