1、题目描述

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

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

2、初始思路

2.1 思路

前序遍历中第一个节点为根节点，根据根节点可以在中序遍历中分辨出来左子树和右子树的节点，然后按照相同的方法，可以构建左子树和右子树的子树。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:#方便查找根节点的位置dic = {}for i in range(len(inorder)):dic[inorder[i]] = idef tree(root,left,right):if left > right:return#节点在前序遍历中的位置索引i = dic[preorder[root]]node = TreeNode(preorder[root])#见图node.left = tree(root+1,left,i-1)node.right = tree(i-left+root+1,i+1,right)return nodereturn tree(0,0,len(preorder)-1)

 以下为node.left = tree(root+1,left,i-1)，node.right = tree(i-left+root+1,i+1,right)的图解。