前言今天继续二叉树相关的算法话题。输入某棵二叉树的前序遍历和中序遍历的结果，请重建二叉树。假设输入的前序遍历和中序遍历的结果都不包含重复数。例如给定前序遍历preorder=[3,9,20,15,7]inorder遍历inorder=[9,3,15,20,7]返回如下二叉树：3/\920/\157说到pre-前序遍历和后序遍历，其实前序、中序、后序都是相对于中间节点的处理顺序。比如前序遍历的顺序应该是：[rootnode|左子树|右子树]同理，中序遍历的顺序为：[左子树|根节点|右子树]所以第一个元素一定是根节点。那么，我们就可以在中序遍历中找到根节点，并将中序遍历正确的分为三部分，即左子树的中序，根节点，左子树的中序右子树。比如：如果只有三个元素，那么到这里就可以结束了，因为树已经可以画好了。例如，前序为[3,9,20]，中序为[9,3,20]。我们根据inorder知道根节点3，然后我们可以区分左子树节点9和inorder中的根节点3，右子树节点20。现在我们展开，如果超过3个节点怎么办？例2：如果有5个元素，比如前序为[3,9,20,15,7]，中序为[9,3,15,20,7]]第一次拆分后，我们划分inorder分为左子树9，根节点3，右子树[15,20,7]这时候右子树应该怎么划分呢？什么是根节点？我不再知道了。所以这个时候，我们需要连接到前序遍历。根据我们已知的左子树节点，可以得出前序中的右子树应该是[20,15,7]，所以右子树的根节点是20。简而言之，前序和中序互相帮助，最终通过递归完成我们这棵树的构建。解决方案1??解决方案1是依赖递归。递归的过程就是找到每个父节点的左子树节点和右子树节点，一共三个值。而最后的值是从前面的序列表中取的，其实就是取每棵小树的父节点。中序遍历数组的作用是找到中序遍历数组中每个父节点的位置。得到以下算法。/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(intx){val=x;}*}*/classSolution{int[]preorder;HashMapdic=newHashMap<>();publicTreeNodebuildTree(int[]preorder,int[]inorder){this.preorder=preorder;for(inti=0;iright)returnnull;//根节点TreeNodenode=newTreeNode(preorder[root]);//分割点inti=dic.get(preorder[root]);node.left=recur(root+1,left,i-1);node.right=recur(root+i-left+1,i+1,right);returnnode;其中，每次取右子树的根节点，需要注意：左子树的节点个数为i-left。因此，在前序遍历数组中，左子树的节点+根节点的位置就是左子树最后一个节点的位置，即root+i-left。最后得到右子树的根节点：root+i-left+1递归的结束条件是左右子树节点满足，即left>right。时间复杂度O(n)，其中n是树中的节点数。空间复杂度O(N)，使用HashMap。解决方案2还有另一种方法称为迭代法。这个方法很巧妙。看了半天官方的解决方案才想通，哈哈。它的主要思想是理解前序遍历和中序遍历的规则，然后从前序遍历中一个一个取值，放到合适的位置。例如下面的二叉树：3/\920//\8157/\510/4前序遍历，可以发现最左边的节点排在最前面，即3,9,8,5,4和第中间的序列表是反向的，从最左边的底部开始往上走。如果发现一个节点有右子节点，则开始向右移动。像4,5,8。此时发现8有右子节点，于是开始数到10，然后从最左边继续往上，9,3。最后列出完整的前序和inorder:preorder=[3,9,8,5,4,10,20,15,7]inorder=[4,5,8,10,9,3,15,20,7]总之，预购开始从左列开始，从上到下。顺序是从左边的列开始，从下到上。看代码：classSolution{publicTreeNodebuildTree(int[]preorder,int[]inorder){if(preorder==null||preorder.length==0){returnnull;}TreeNoderoot=newTreeNode(preorder[0]);Dequestack=newLinkedList();stack.push(root);intinorderIndex=0;for(inti=1;i
