题解 | #重建二叉树#

1、找终止条件：树为空的时候，此时没有子树序列，递归就结束了。

2、找返回值：返回值应该是当前树的根节点。

3、本递归应该做什么：判断根节点，接着判断左右子树，本题是要重建二叉树，因此在每级递归中，将左右子树连接在根节点上即可。

class Solution:
    def reConstructBinaryTree(self , pre: List[int], vin: List[int]) -> TreeNode:
        # write code here
        if not pre or not vin:
            return None
        #构造根节点，寻找左右子树的分界线
        root = TreeNode(pre[0])
        n = vin.index(pre[0])
        #构造左右子树，递归调用
        root.left = self.reConstructBinaryTree(pre[1:n + 1], vin[:n])
        root.right = self.reConstructBinaryTree(pre[n + 1:], vin[n + 1:])
        #返回根节点
        return root