题目描述
给定某二叉树的前序遍历和中序遍历，请重建出该二叉树并返回它的头结点。
方法一： 递归
解题思路
前序遍历的第一个节点就是这颗树的根节点。
在中序遍历中，找到这个根节点，这个根节点的左边元素就是它的左子树上的元素，这个根节点的右边元素就是它的右子树上的元素。
把范围划分好，直到范围上只有一个元素直接生成返回即可。
需要找到根节点在中序遍历上的下标，才能知道它的左子树上有多少个元素，右子树上有多少个元素。为了方便找到下标，可以用 Map 结构来存储 中序遍历数组上 所有元素和其下标 的对应关系。
以下是以 前序遍历为：[8，3，6，7，9] ， 中序遍历为：[3，6，8，9，7] 的演示图：
复杂度分析
时间复杂度：O(N*logN)
需要挨个递归遍历每个元素，总共有 N 个元素;
另外在遍历每个元素的时候，用到了 HashMap 的查找操作，虽然可以认为他的查询操作一般情况下是 O(1) 级别的时间复杂度。但底层可能是链表存储，这样的查询操作的时间复杂度为 O(N)；也可能是红黑树存储，这样的查询操作的时间复杂度为 O(logN)；（采用哪种存储结构和存储的数量有关）
而这里 Map 的结果是有序的，数据量为 N 也不好确定具体是多少，所以最后的时间复杂度为：O(N*logN)。
空间复杂度：O(N)
重建整颗二叉树需要建立每一个节点，总共有 N 个节点，所以空间复杂度为 O(N)
代码示例
import java.util.*;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
// 判断特殊情况
if (pre == null || pre.length == 0 || in == null || in.length == 0) {
return null;
}
// key ： 中序遍历元素的值；
// value ： 中序遍历元素的值 对应的 下标
// 可以以O(1)的时间复杂度找到元素在中序遍历中对应的下标
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < in.length; i++) {
map.put(in[i], i);
}
// 返回在 pre[0...pre.length-1] , in[0, in.length-1] 范围上建立二叉树的根节点
return process(pre, 0, pre.length - 1,
0, in.length - 1,
map);
}
/**
* @param pre 前序遍历的数组
* @param pL 使用到的 前序遍历的数组 的左边界，闭区间
* @param pR 使用到的 前序遍历的数组 的右边界，闭区间
* @param inL 使用到的 中序遍历的数组 的左边界，闭区间
* @param inR 使用到的 中序遍历的数组 的右边界，闭区间
* @param map 方便找到元素在中序遍历中对应的下标 需要的 数据结构
* @return 在使用到的 前序遍历数组、中序遍历数组中；生成该范围内的二叉树，返回这个二叉树的 根节点
*/
public TreeNode process(int[] pre, int pL, int pR,
int inL, int inR,
HashMap<Integer, Integer> map) {
// 越界情况，没有二叉树存在，直接返回 null
if (pL > pR || inL > inR) {
return null;
}
// 只有一个元素，就是根节点，直接返回
if (pL == pR || inL == inR) {
return new TreeNode(pre[pL]);
}
// 前序遍历的第一个元素就是 根节点
TreeNode root = new TreeNode(pre[pL]);
// 找到 根节点在 中序遍历数组里的 下标
int inIndex = map.get(pre[pL]);
// 在有效的中序遍历范围里， 根节点左边的元素 都是属于 根节点的左子树
int leftTreeSize = inIndex - inL;
// 在左子树的有效范围里，生成左子树
root.left = process(pre, pL + 1, pL + leftTreeSize,
inL, inIndex - 1,
map);
// 在右子树的有效范围里，生成右子树
root.right = process(pre, pL + leftTreeSize + 1, pR,
inIndex + 1, inR,
map);
return root;
}
} 方法二： 用栈
解题思路
虽然递归方法都可以改写成为非递归的方法实现，但还是要具体问题具体分析。
就该题来说，先了解前序遍历和中序遍历的特点：
前序遍历： 顺序就是所有第一次访问到根节点时的顺序，
如果一个元素有左子树，那么下一个元素的值就是它的左子树的值；
如果没有左子树，就看之前访问的哪个元素有右子树，那么下一个元素的值就是“之前访问有右子树的元素”的那个右子树的值。
中序遍历：顺序就是所有第二次访问到根节点时的顺序。
我们可以结合中序遍历的结果，进而找到具体的哪个元素有右子树，具体思路参照代码流程及注释。
所以，整个流程就是遍历一遍前序遍历的数组，生成相对应的左子树；再结合中序遍历，生成相对应的右子树。
以下是以 前序遍历为：[8，3，6，7，9] ， 中序遍历为：[3，6，8，9，7] 的演示图：
复杂度分析
时间复杂度： O(N)
整个的大流程就是一个 for 循环遍历前序数组，虽然里面有一个 while 循环，但这个 while 循环极端情况下只会发生在前序遍历的某一个元素上，并不是所有元素都会进入 while 循环中，所有时间复杂度为 O(N)。
空间复杂度：O(N)
重建整颗二叉树需要建立每一个节点，总共有 N 个节点，所以空间复杂度为 O(N)
示例代码
import java.util.*;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
// 判断特殊情况
if (pre == null || pre.length == 0 || in == null || in.length == 0) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
int preIndex = 0;
int inIndex = 0;
// 整颗树的根节点
TreeNode root = new TreeNode(pre[preIndex]);
stack.push(root);
// 遍历 前序遍历的数组， 生成对应的根节点
for (preIndex = 1; preIndex < pre.length; preIndex++) {
TreeNode node = stack.peek();
// 之前压栈的元素 不等于 中序遍历数组中开头的数，
// 即 之前压栈的元素 有左子树
if (node.val != in[inIndex]) {
// 再生成相应的左子树并压栈
node.left = new TreeNode(pre[preIndex]);
stack.push(node.left);
} else {
// 之前压栈的元素的值 等于 中序遍历数组中开头的数，
// 即 之前压栈的元素 没有左子树； 继续找那个元素有右子树
while (!stack.isEmpty() && stack.peek().val == in[inIndex] ) {
node = stack.pop();
inIndex++;
}
// 再生成相应的右子树并压栈
node.right = new TreeNode(pre[preIndex]);
stack.push(node.right);
}
}
// 返回整棵树的根节点
return root;
}
} 
京公网安备 11010502036488号