105：从前序与中序遍历序列构造二叉树

啊，好久都没有更新算法题目了。曾今是C++，如今是Java，感慨啊。

像树这样的算法题，基本都逃不开递归。递归的思想是：将大任务拆分为小任务。我们不妨构建一个函数，取名func1()，它实现的功能是:在指定区间内, 找到并构建root节点并返回。

如果我们想要构建一棵树，只需要调用func1()，就能够得到树的根节点，那么树的构建过程就可以简化为如下形式:

TreeNode root = new TreeNode();
root.value = value;
root.left = func1(...);
root.right = func1(...)'

通过func1，我们即可计算得到左右节点，具体的逻辑都一样

现在，让我们将视角聚焦于如何构建func1()。函数内容的核心是：构建root节点。构建分为三步: 1.得到root.val，构建root.left，构建root.right。为了解决这个内容，我们先将 前序遍历，中序遍历写为以下形式

前序 ： 【root，（左子树），（右子树）】
中序 ： 【（左子树），root，（右子树）】

如果我们想要确定root节点，我们只需要在前序数组中，获取第一个元素即可。如果我们想要确定左子树长度，右子树长度，我们只需要知道中序中，root节点的index即可

我们假设前序数组的区间范围是：$[l1,r1]$，中序是：$[l2,r2]$。root节点在中序的下标是$rootIdxIn$，那么左子树长度$lefLen=rootIndIn-l2$，右子树长度$rigLen=r2-rootIndIn$

rootValue很好获取，前序[l1]。
root.left的获取，我们可以交给递归函数完成。因为root.left，其本质是左子树的root节点，规定func1的计算范围是root节点的左子树范围即可完成计算；
root.right同理。

tip : 笔者习惯将递归函数命名为dfs，但这不是真正的dfs

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public HashMap<Integer, Integer> map = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;// 通过map映射 值-index的方式, 加速root节点在中序数组下标的定位速度for (int i = 0; i < inorder.length; ++i) {map.put(inorder[i], i);}return dfs(preorder, inorder, 0, n - 1, 0, n - 1);}public TreeNode dfs(int[] preorder, int[] inorder, int l1, int r1, int l2, int r2) {// 递归终止条件, 如果l1 > r1, 表明当区间不存在, 节点值应该赋为nullif (l1 > r1 || l2 > r2) return null;// debugSystem.out.println("l1 = " + l1 + " r1 = " + r1 + " l2 = " + l2 + " r2 = " + r2);// 确定根节点int rootVal = preorder[l1];// 根节点再inorder中的indexint rootIdxIn = map.get(rootVal);System.out.println("rootIdxIn = " + rootIdxIn);// 左区间长度int lefLen = rootIdxIn - l2;// 右区间长度int rigLen = r2 - rootIdxIn;TreeNode root = new TreeNode();root.val = rootVal;root.left = dfs(preorder, inorder, l1 + 1, l1 + lefLen, l2, rootIdxIn - 1);root.right = dfs(preorder, inorder, l1 + lefLen + 1, r1, rootIdxIn + 1, r2);return root;}
}