105. 从前序与中序遍历序列构造二叉树
给定两个整数数组
preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
为什么存值下标，不是下标值————HashMap.get(Object key)方法，传入 key 即可返回对应的 value
class Solution {private Map<Integer, Integer> map;public TreeNode buildTree(int[] preorder, int[] inorder) {map = new HashMap<>();int n = inorder.length;// 存储中序遍历中“值-下标”的映射for (int i = 0; i < n; i++) {map.put(inorder[i], i);}// 调用递归构建方法return build(preorder, 0, n - 1, inorder, 0, n - 1);}// 递归构建二叉树的核心方法// preLeft/preRight：先序数组当前区间的左右边界// inLeft/inRight：中序数组当前区间的左右边界public TreeNode build(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {// 递归终止条件：区间无效（左边界超过右边界）if (preLeft > preRight || inLeft > inRight) {return null;}// 1. 先序遍历的第一个元素就是当前子树的根节点int preRootIdx = preLeft;int rootVal = preorder[preRootIdx];TreeNode root = new TreeNode(rootVal);// 2. 找到根节点在中序遍历中的下标（这就是HashMap的核心作用）int inRootIdx = map.get(rootVal);// 3. 计算左子树的节点个数（中序数组中根节点左侧的元素都是左子树）int leftSubtreeSize = inRootIdx - inLeft;// 4. 递归构建左子树// 先序左子树区间：[preLeft+1, preLeft+leftSubtreeSize]// 中序左子树区间：[inLeft, inRootIdx-1]root.left = build(preorder, preLeft + 1, preLeft + leftSubtreeSize,inorder, inLeft, inRootIdx - 1);// 5. 递归构建右子树// 先序右子树区间：[preLeft+leftSubtreeSize+1, preRight]// 中序右子树区间：[inRootIdx+1, inRight]root.right = build(preorder, preLeft + leftSubtreeSize + 1, preRight,inorder, inRootIdx + 1, inRight);return root;} }
【背！！！一点不会】