题目描述

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

解题思路

前序遍历的第一个值为根结点的值，将中序遍历序列分为左右两个部分，左边为左子树中序遍历的结果，右边为右子树中序遍历的结果，使用递归重复以上过程。

  1. # -*- coding:utf-8 -*-
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. class Solution:
  8.     # 返回构造的TreeNode根节点
  9.     def reConstructBinaryTree(self, pre, tin):
  10.         # write code here
  11.         if not pre or not tin:
  12.             return None
  13.         #确立根结点
  14.         root=TreeNode(pre[0])
  15.         index=tin.index(pre[0])
  16.         #确立左子树
  17.         root.left=self.reConstructBinaryTree(pre[1:index+1], tin[:index])
  18.         #确立右子树
  19.         root.right=self.reConstructBinaryTree(pre[index+1:], tin[index+1:])
  20.         return root