已知二叉树的中序和前序序列(或后序)求解树

这种题一般有二种形式，共同点是都已知中序序列。如果没有中序序列，是无法唯一确定一棵树的，证明略。
一、已知二叉树的前序序列和中序序列，求解树。
步骤：
1.定位树根节点：从前序列表可以知道第一个元素为树根
2.求树的左右子树：从中序列表以步骤1中的树根为中心，左边为左子树，右边为右子树
3.递归求解：分别以左右子树，重复步骤1，2，3，直到所有节点都定位完成。

二、已知二叉树的后序序列和中序序列，求解树。
步骤：
1.定位树根节点：从后序列表可以知道最后一个元素为树根
2.求树的左右子树：从中序列表以步骤1中的树根为中心，左边为左子树，右边为右子树
3.递归求解：分别以左右子树，重复步骤1，2，3，直到所以节点都定位完成。

以下为python的示例代码

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

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.value = val
        self.left = left
        self.right = right

    def prev_visit(self, result):
        """鍓嶅簭閬嶅巻"""
        result.append(self.value)
        if self.left:
            self.left.prev_visit(result)
        if self.right:
            self.right.prev_visit(result)

    def midd_visit(self, result):
        if self.left:
            self.left.midd_visit(result)
        result.append(self.value)
        if self.right:
            self.right.midd_visit(result)

    def post_visit(self, result):
        if self.left:
            self.left.post_visit(result)
        if self.right:
            self.right.post_visit(result)
        result.append(self.value)

    def level(self):
        left_level = 0
        right_level = 0
        if self.left:
            left_level = self.left.level()
        if self.right:
            right_level = self.right.level()

        return 1 + (left_level if left_level > right_level else right_level)

def from_before_and_middle(before, middle):
    if len(before) == 1:
        return TreeNode(before[0])
    val = before[0]
    idx = middle.index(val)
    left = None
    right = None
    left_middle = None
    right_middle = None
    if idx > 0:
        left_middle = middle[0:idx]
        left = from_before_and_middle([i for i in before if i in left_middle], left_middle)

    if idx < (len(middle)-1):
        right_middle = middle[idx+1:]
        right = from_before_and_middle([i for i in before if i in right_middle], right_middle)

    #print "before:", before
    #print "middle:", middle
    #print "root:", val, "left:", left_middle, "right:", right_middle
    return TreeNode(val, left, right)

def from_post_and_middle(post, middle):
    if len(post) == 1:
        return TreeNode(post[0])
    val = post[-1]
    idx = middle.index(val)
    left = None
    right = None
    left_middle = None
    right_middle = None
    if idx > 0:
        left_middle = middle[0:idx]
        left = from_post_and_middle([i for i in post if i in left_middle], left_middle)

    if idx < (len(middle)-1):
        right_middle = middle[idx+1:]
        right = from_post_and_middle([i for i in post if i in right_middle], right_middle)

    #print "post:", post
    #print "middle:", middle
    #print "root:", val, "left:", left_middle, "right:", right_middle
    return TreeNode(val, left, right)

if __name__ == '__main__':
    before = [1, 2, 4, 5, 7, 9, 10, 3, 6, 8]
    middle = [4, 2, 9, 7, 10, 5, 1, 3, 8, 6]
    tree = from_before_and_middle(before, middle)
    post = []
    tree.post_visit(post)
    print post
    print "level:", tree.level()
    tree = from_post_and_middle(post, middle)
    before_2 = []
    tree.prev_visit(before_2)
    if before_2 == before:
        print "success"