剑指04-重建二叉树

题目描述

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

---

• 可以唯一确定一棵树的遍历组合是先序和中序和后续和中序；而先序和后续不能唯一确定一棵树。

思路：

• 先由先根序列的第一个字符将中根序列分为左右两个子序列，该字符为根节点，左序列是左子树的中根遍历序列，右序列是右子树的中根遍历序列。
• 由左序列和左序列里字符在先根序列中的先后序列，可以用递归的方式得到左子树；同样的方式可以获得右子树。
• 一个特性：深度优先遍历里，左子树和右子树的打印序列不会有交叉。

class Solution:
    def rebuild(self, pre, tin):
        if len(pre) != len(tin) or pre is None or len(pre) == 0:
            return None
        root = TreeNode(pre[0])
        mid = tin.index(pre[0])
        root.left = self.rebuild(pre[1:mid+1], tin[:mid])
        root.right = self.rebuild(pre[mid+1:], tin[mid + 1:])
        return root