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

题目

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

题解

1. 根据前序确定根节点
2. 根据中序确定左子树和右子树
3. 再重复之前的操作（左子树：前序和中序，右子树：前序和中序）

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def buildTree(self, preorder, inorder):""":type preorder: List[int]:type inorder: List[int]:rtype: Optional[TreeNode]"""if len(preorder) == 0:return Noneroot_value = preorder[0]root = TreeNode(root_value)if len(preorder) == 1:return rootindex = 0    for i in range(len(preorder)):if inorder[i] == root_value:index = ibreakin_left = inorder[:index]in_right = inorder[index + 1:]pre_left = preorder[1: len(in_left) + 1]pre_right = preorder[len(in_left) + 1:]root.left = self.buildTree(pre_left, in_left)root.right = self.buildTree(pre_right, in_right)return root