力扣105——从前序与中序遍历序列构造二叉树
原题
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
原题url：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
解题
这道题目，主要就是在于大家对于二叉树这个数据结构的熟悉程度了，根据其前序遍历和中序遍历，推算出原本的二叉树。
我们想想，如果不是写代码，只是通过手写的话，我们是如何查找的，就用题目给出的例子：
根据前序遍历，第一个一定是根节点，那么 3 就是根节点。
从中序遍历中寻找 3，在它左边的，都是其左子树上的节点，在它右边的，都是其右子树上的节点。
因为中序遍历中，3 的左边只有9，那么 9 就是 3 的左子节点。
根据前序遍历
先根然后左子节点，然后再右子节点的规律，3 、9 之后的 20 一定是 3 的右子节点。20 在中序遍历中，其左右两边就是 15 和 7，因此15 和 7 就分别是它的左右子节点。
根据上面的分析，你就可以画出例子中的二叉树了。
那么我们寻找的顺序是，先从前序遍历的第一个节点开始，在中序遍历中找出它的位置，其左右两边就是其左右子树了，
接着从左子树入手，前序遍历根节点之后的两个节点应该就是其左右子树，但需要考虑没有左右子树的情况，然后再以其子树为根，在中序遍历中找其左右子树。
需要注意的是，只有针对根节点，其左右子节点是在前序遍历中紧跟着根节点的，其他都是有距离的，需要根据左子树递推。
接下来看看代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int[] preorder;
int[] inorder;
// preorder中遍历过的数量，这样找完左子树中的节点，剩下的第一个节点，必然是右子节点
int preorderIndex = 0;
// key为inorder中的值，value为inorder中的下标
Map<Integer, Integer> inorderMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) {
return null;
}
TreeNode node = new TreeNode(preorder[0]);
if (preorder.length == 1) {
return node;
}
this.preorder = preorder;
this.inorder = inorder;
this.inorderMap = new HashMap<>(inorder.length * 4 / 3 + 1);
for (int i = 0; i < inorder.length; i++) {
this.inorderMap.put(inorder[i], i);
}
return generateNode(0, inorder.length);
}
/**
* 寻找当前节点的左右子节点
* start：inorder里开始寻找的节点下标
* end：inorder里终止寻找的节点下标
* preorderIndex：当前节点在preorder中的下标
*/
public TreeNode generateNode(int start, int end) {
if (start >= end) {
return null;
}
// 当前节点
int value = preorder[preorderIndex];
TreeNode node = new TreeNode(value);
// 当前节点的值，在inorder中的下标
int inorderIndex = inorderMap.get(value);
// 当前节点已经找到，寻找下一个节点。
// 因为会先去寻找左节点，当该节点左子树中所有节点全部找完后，前序遍历中，剩下节点的第一个节点，一定是该节点的右节点。
preorderIndex++;
// 寻找左节点
node.left = generateNode(start, inorderIndex);
// 寻找右节点
node.right = generateNode(inorderIndex + 1, end);
return node;
}
}
提交OK，执行用时：3 ms，内存消耗：40.1 MB。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题目主要就是寻找规律，优化的话，可能就是利用 map 构造中序遍历中节点值和顺序的关系。
有兴趣的话可以访问我的博客或者关注我的公众号，说不定会有意外的惊喜。
https://death00.github.io/
公众号：健程之道