2.1 思路分析
由数组的前序遍历和中序遍历可以确定一颗树的结构；关于递归的终止条件，为了不改变数组大小，利用startPre、endPre来限制前序数组的递归范围，利用startIn、endIn来限制中序数组的递归范围，当startPre > endPre或者startIn > endIn时，递归退出；定义结点，保存树(或子树)递归进来的根结点；遍历中序数组的递归范围，即[startIn，endIn]，确定根结点在中序数组中的位置 i；找到后，对3中根结点递归其左子树，即对其左子树进行前序和中序遍历，对于前序遍历，其递归的范围为[startPre+1，startPre + i - startIn]，解释一下：startPre一开始的定位即为前序数组的根结点，既然要递归左子树，那么找到左子树的根结点，那么根据前序数组，左子树的根结点的定位即为startPre+1；对于中序遍历，其递归的范围为[startIn，i - 1]，解释一下：中序数组的前半部分就是左子树，其起点为startIn，因为i是根结点在中序数组中的位置，所以要到 i - 1；递归完左子树，再递归右子树的前序和中序遍历，对于前序遍历，其递归范围为[startPre + i - startIn +1，endPre]，也就是定位到前序数组中右子树的起点和终点；对于中序遍历，其递归范围为[i + 1，endIn]，同样也是定位到中序数组中右子树的起点和终点。2.2 代码实现
class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { return help(preorder,0,preorder.length-1,inorder,0,inorder.length-1); } public TreeNode help(int[] pre,int startPre,int endPre,int[] in,int startIn,int endIn) { if(startPre > endPre || startIn > endIn) { return null; } TreeNode node = new TreeNode(pre[startPre]); for(int i = startIn; i <= endIn; i++) { if(in[i] == pre[startPre]) { node.left = help(pre,startPre+1,startPre+i-startIn,in,startIn,i-1); node.right = help(pre,startPre+i-startIn+1,endPre,in,i+1,endIn); } } return node; } }2.3 复杂度分析
时间复杂度为O(n)；空间复杂度为O(n)；2.4 参考地址
https://www.cnblogs.com/MrSaver/p/9205436.html
3.1 思路分析
为了不修改原数组，定义新数组，获取前序数组的地址；利用HashMap集合，存储中序数组的值和对应的下标，目的是为了方便找到前序数组中根结点在中序数组中的下标；单独写一个递归函数，并返回；递归函数返回值为TreeNode，参数传入前序数组中的根结点下标以及中序数组的起止下标；递归的终止条件，仍然是以中序数组的起止下标为准，然后新建结点，保存传进来的根结点，然后利用集合和传进来的根结点值，找到该值再中序数组中对应的下标，这个下标的左边就是左子树，右边就是右子树；递归当前根结点的左子树和右子树，关于参数范围，前面已有介绍，这里不再赘述。3.2 代码实现
class Solution { HashMap<Integer, Integer> dic = new HashMap<>(); int[] po; public TreeNode buildTree(int[] preorder, int[] inorder) { po = preorder; for(int i = 0; i < inorder.length; i++) dic.put(inorder[i], i); return recur(0, 0, inorder.length - 1); } TreeNode recur(int pre_root, int in_left, int in_right) { if(in_left > in_right) return null; TreeNode root = new TreeNode(po[pre_root]); int i = dic.get(po[pre_root]); root.left = recur(pre_root + 1, in_left, i - 1); root.right = recur(pre_root + i - in_left + 1, i + 1, in_right); return root; } }2.3 复杂度分析
时间复杂度为O(n)；空间复杂度为O(n)；2.4 参考地址
https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-di-gui-fa-qin/
