DESC:

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
9 20
    / \
   15   7

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

CODE1:

JAVA:

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public TreeNode buildTree(int[] preorder, int[] inorder) {        if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) {            return null;        }        TreeNode root = new TreeNode(preorder[0]);        for (int i=0; i

NOTE1:

递归，dfs

前序遍历首位肯定是根节点值，在中序遍历找到该根节点值位置(二叉树无重复值是前提)，则在位置左边便是所有的左节点，右侧有所有的右节点，且都是中序排序，并根据索引位置可知道左节点数；

根据左节点数，可找到左节点的前序遍历，中序遍历，将其放到方法中递归调用，则得到根节点的左节点，同理，可得到右节点；

注意边界，前开后闭

CODE1在每次查找根节点位置时，都需要遍历对应的中序进行查找，效率较低，优化。。。

CODE2:

JAVA:

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public Map
    
      inorderIndexMap = new HashMap();    public TreeNode buildTree(int[] preorder, int[] inorder) {        if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) {            return null;        }        for (int i=0; i
     
       preRight) {            return null;        }        int rootVal = preorder[preLeft];        TreeNode node = new TreeNode(rootVal);        int midIndex = inorderIndexMap.get(rootVal);        node.left = this.buildTree(preorder, inorder, preLeft+1, preLeft+midIndex-inLeft, inLeft, midIndex-1);         node.right = this.buildTree(preorder, inorder, preLeft+midIndex-inLeft+1, preRight, midIndex+1, inRight);        return node;    }}

NOTE2:

相比code1，这里我们先将中序遍历的值及其位置索引放到map中，便于后面以O(1)的时间复杂度获取根节点的问题，解决code1每次遍历耗时的问题；

因为每次获取的根节点索引都是相对于原始中序结果，所以需要递归中都是相对原始前序或中序结果的位置索引，不像code1中直接将对应的序列截出来递归，所以更需要计算好边界问题，注意参数传递的都是闭区间；