105. 从前序与中序遍历序列构造二叉树

一、105. 从前序与中序遍历序列构造二叉树

1.1、题目描述

1.2.1、递归

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not inorder:
            return
        # 前序遍历，第一个节点是根节点
        root = TreeNode(preorder.pop(0))
        # 在中序遍历， 根节点分割左右子树
        i = inorder.index(root.val)
        
        root.left = self.buildTree(preorder, inorder[:i])
        root.right = self.buildTree(preorder, inorder[i+1:])
        return root