难度：中等

题目：

给定两个整数数组 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:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 无重复 元素
• inorder 均出现在 preorder
• preorder 保证 为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

 Related Topics

• 树
• 数组
• 哈希表
• 分治
• 二叉树

 重点！！！解题思路

第一步： 

这道题我们使用递归和栈的思想来解决此题

前序遍历：根左右，中序遍历，左右根。

我们能很容易的得到前序遍历的根节点，但是不容易拿到中序遍历根节点的下标

所以我们首先采用map集合来存储中序遍历的节点值

第二步：

使用递归来创建根节点下的每个节点

明白上述思路即可实现此题 

源码+讲解：

class Solution {Map map;public TreeNode buildTree(int[] preorder, int[] inorder) {map = new HashMap<>();  //存储inorder的所有节点for (int i=0;ip_end) return null;  //空节点的返回TreeNode root = new TreeNode(preorder[p_start]);  //节点创建int mid = map.get(preorder[p_start]);//获得根节点int leftNum=mid-i_start;//根据中序遍历来得到左子树的长度root.left=helper(preorder,inorder,p_start+1,p_start+leftNum,i_start,mid-1);root.right=helper(preorder,inorder,p_start+leftNum+1,p_end,mid+1,i_end);return root;}
}

运行结果：

如果您还有什么疑问或解答有问题，可在下方评论，我会及时回复。 

系列持续更新中，点个订阅吧