1、二叉树前序、中序，构建完整二叉树并后序遍历输出

#!/usr/bin/env python
# -*- coding: utf-8 -*-
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.right = None
        self.left = None

class Solution:
    def rebuildTree(self, preorder, inorder):
        adict = {}
        for i in range(len(inorder)):
            adict[inorder[i]] = i
        self._preorder = preorder
        self._inorder = inorder
        def dfs(pl, pr, il, ir):
            if pl > pr:
                return None
            root_val = self._preorder[pl]
            root = TreeNode(root_val)
            pos = adict[root_val]
            left = dfs(pl+1, pl+1+pos-il-1, il, pos-1)
            right = dfs(pl+pos-il+1, pr, pos+1, ir)

            root.left = left
            root.right = right
            return root
        root = dfs(0, len(preorder)-1, 0, len(inorder)-1)
        return root

if __name__ == '__main__':
    solution = Solution()
    preorder = [1, 2, 4, 3, 5]
    inorder = [4, 2, 1, 3, 5]
    res = solution.rebuildTree(preorder, inorder)

2、编辑距离