题解 | #重建二叉树#
重建二叉树
http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
【剑指offer】重建二叉树（python）
记住没有中序遍历结果是不能重建二叉树的！
- 二叉树的左中后遍历顺序。
前序遍历：根结点 ---> 左子树 ---> 右子树
中序遍历：左子树---> 根结点 ---> 右子树
后序遍历：左子树 ---> 右子树 ---> 根结点
前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1 - 根据前序和中序遍历重建二叉树。
前序中第一位是根节点，在中序中定位出根节点，左边就是左子树，右边是右子树，得到左子树的长度后，在前序序列中确认左子树的序列，第一位定位到左子树的根节点，继续在中序中定位出根节点，分出左右子树，持续递归。递归结束条件是序列为空。
关键在于从前序遍历序列中得到根节点，从而在中序遍历序列中得到左子树长度，进一步在前序序列中定位到左子树及其根节点位置。# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # 返回构造的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): if len(pre)==0:return None root=ListNode(pre[0]) pos=tin.index(pre[0]) root.left=self.reConstructBinaryTree(pre[1:pos+1], tin[:pos]) root.right=self.reConstructBinaryTree(pre[pos+1:],tin[pos+1:]) return root
