18. 重建二叉树

问题描述

输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

注意:

• 二叉树中每个节点的值都互不相同；
• 输入的前序遍历和中序遍历一定合法；

样例

给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：
    3
   / \
  9  20
    /  \
   15   7

解决方案

思路：前序的第一个元素是根结点的值，在中序中找到该值，中序中该值的左边的元素是根结点的左子树，右边是右子树，然后递归的处理左边和右边

不太理解的话需要配合示意图来看：

https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/7/

class Solution(object):
    def buildTree(self, preorder, inorder):
        if not preorder or not inorder:
            return None

        index = inorder.index(preorder[0])  # 找到前序遍历结果中第一位对应在中序遍历结果中的位置
        left = inorder[0:index]
        right = inorder[index+1:]
        root = TreeNode(preorder[0])
        root.left = self.buildTree(preorder[1:1+len(left)], left)
        root.right = self.buildTree(preorder[-len(right):], right)
        return root