原题输入一棵二叉树的前序遍历和中序遍历的结果，构建二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果都不包含重复数。credittoLeetcodeIdeas先回顾一下前序遍历和中序遍历。对于图中的情况，我们可以得到：pre-order:[root,left,right]=>[3,9,20,15,7]in-order:[Left,root,right]=>[9,3,15,20,7]最重要的一点是理清思路，先序和中序的规则前序排在第一位的是树的根节点，这个根节点在中序中，它会出现在任何位置。这里不难发现根节点[3]在中序遍历结果中有一个不寻常的意义：根节点[3]左边的点是左子树，根节点右边的点是右子树。回到前序遍历，我们也可以将前序遍历结果中的根和两个子树进行划分，为后面的递归做准备，[3][9][20,15,7]然后进行递归过程左子树和右子树的关系，比如这里的右子树，我们可以再次执行步骤1的方法，确定子树的根节点和两个子树，发现根节点是第一个[20]，然后返回中序遍历找到[20]的位置，发现原来的右子树可以分为[15]、[20]、[7]两个子树。这时候算法设计就完全遍历了，因为每次从前序结果中找到一个新的根节点，我们都要回到中序遍历来划分子树，所以创建一个哈希表来存储值以及每个节点的索引，方便递归索引搜索，我们设置索引为k。对于递归函数，我们可以新建一个recur，参数分别是，前序的根索引root，中序的左边界left，中序的右边界。当left>right时，表示没有下一个节点如何创建，返回null接下来是最关键的部分，如何递归计算根节点的左子树和右子树，这里有一张表来体现：Preorder:rootindexinorder:leftboundaryinorder:rightboundaryleftsubtreeroot+1leftk-1rightsubtreek-left+root+1k+1right这里k-left+root+1其实就是左子树长度+root+1的编码实现/***二叉树节点的定义。*functionTreeNode(val){*this.val=val;*this.left=this.right=null;*}*//***@param{number[]}preorder*@param{number[]}inorder*@return{TreeNode}*/varbuildTree=function(preorder,inorder){constdic=newMap()对于(leti=0;i
