「力扣」第 105 题：从前序与中序遍历序列构造二叉树（中等）
抓住「前序遍历序列」与「中序遍历序列」的定义，递归构建二叉树。并且通过画图计算出需要使用的子区间的下标。最后看一眼复杂度，使用「空间换时间」的思路优化。
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：
3 / \ 9 20 / \ 15 7
方法：分治算法
- 结合「前序遍历序列」和「中序遍历序列」的定义；
- 前序遍历的第 1 个结点一定是二叉树的根结点；
- 在中序遍历中，根结点把中序遍历序列分成了两个部分，左边部分构成了二叉树的根结点的左子树，右边部分构成了二叉树的根结点的右子树。
最初版本：为了找到根结点在「中序遍历序列」中的下标，使用了遍历，复杂度较高。
Java 代码：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preLen = preorder.length;
int inLen = inorder.length;
if (preLen != inLen) {
throw new RuntimeException("Incorrect input data.");
}
return buildTree(preorder, 0, preLen - 1, inorder, 0, inLen - 1);
}
/**
* 使用数组 preorder 在索引区间 [preLeft, preRight] 中的所有元素
* 和数组 inorder 在索引区间 [inLeft, inRight] 中的所有元素构造二叉树
*
* @param preorder 二叉树前序遍历结果
* @param preLeft 二叉树前序遍历结果的左边界
* @param preRight 二叉树前序遍历结果的右边界
* @param inorder 二叉树后序遍历结果
* @param inLeft 二叉树后序遍历结果的左边界
* @param inRight 二叉树后序遍历结果的右边界
* @return 二叉树的根结点
*/
private TreeNode buildTree(int[] preorder, int preLeft, int preRight,
int[] inorder, int inLeft, int inRight) {
// 因为是递归调用的方法，按照国际惯例，先写递归终止条件
if (preLeft > preRight || inLeft > inRight) {
return null;
}
// 先序遍历的起点元素很重要
int pivot = preorder[preLeft];
TreeNode root = new TreeNode(pivot);
int pivotIndex = inLeft;
// 严格上说还要做数组下标是否越界的判断 pivotIndex < inRight
while (inorder[pivotIndex] != pivot) {
pivotIndex++;
}
root.left = buildTree(preorder, preLeft + 1, pivotIndex - inLeft + preLeft,
inorder, inLeft, pivotIndex - 1);
root.right = buildTree(preorder, pivotIndex - inLeft + preLeft + 1, preRight,
inorder, pivotIndex + 1, inRight);
return root;
}
}
复杂度分析：
- 时间复杂度：$O(N^2)$，这里 $N$ 是二叉树的结点个数，每调用一次递归方法创建一个结点，一共创建 $N$ 个结点，在中序遍历中找到根结点在中序遍历中的位置，是与 $N$ 相关的，这里不计算递归方法占用的时间；
- 空间复杂度：$O(1)$，这里不计算递归方法占用的空间。
最终版本：把中序遍历序列中的数值和下标存在哈希表里，方便后面使用。
Java 代码：
import java.util.HashMap;
import java.util.Map;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preLen = preorder.length;
int inLen = inorder.length;
if (preLen != inLen) {
throw new RuntimeException("Incorrect input data.");
}
Map<Integer, Integer> map = new HashMap<>(preLen);
for (int i = 0; i < inLen; i++) {
map.put(inorder[i], i);
}
return buildTree(preorder, 0, preLen - 1, map, 0, inLen - 1);
}
/**
* @param preorder 前序遍历序列
* @param preLeft 前序遍历序列子区间的左边界，可以取到
* @param preRight 前序遍历序列子区间的右边界，可以取到
* @param map 在中序遍历序列里，数值与下标的对应关系
* @param inLeft 中序遍历序列子区间的左边界，可以取到
* @param inRight 前序遍历序列子区间的右边界，可以取到
* @return
*/
private TreeNode buildTree(int[] preorder, int preLeft, int preRight,
Map<Integer, Integer> map, int inLeft, int inRight) {
if (preLeft > preRight || inLeft > inRight) {
return null;
}
int rootVal = preorder[preLeft];
TreeNode root = new TreeNode(rootVal);
int pIndex = map.get(rootVal);
root.left = buildTree(preorder, preLeft + 1, pIndex - inLeft + preLeft,
map, inLeft, pIndex - 1);
root.right = buildTree(preorder, pIndex - inLeft + preLeft + 1, preRight,
map, pIndex + 1, inRight);
return root;
}
}
复杂度分析：
- 时间复杂度：$O(N)$，这里 $N$ 是二叉树的结点个数，每调用一次递归方法创建一个结点，一共创建 $N$ 个结点，这里不计算递归方法占用的时间。
- 空间复杂度：$O(N)$，这里忽略递归方法占用的空间，因为是对数级别的，比 $N$ 小。
