由以下两题展开分析：
为什么前中或者中后能重建，前后能吗？
首先要说明以下为什么单独的前序无法重建：
根据DFS的性质，前序遍历优先往左下探索，直到不能继续则回头寻找右边可走的节点。这种行为给予了前序遍历一个重要性质：
对于前序数组中任意两个连续的节点值x和y，y要么是x的左子节点，要么是x或者x之上某个祖先的右子节点（这里简称为亲戚节点）。
这个性质导致的前序重建的二叉树无法唯一，比如序列12，重建后可以为根节点为1，左节点为2的二叉树，也可以成为根节点为1，右节点为2的二叉树。
所以如果想要重建二叉树的话，只有两种方案：
1.补全空节点的输出。
比如：序列化二叉树
2.非递归，利用中序来判断每一个y是左儿子还是亲戚节点。
3.递归划分子树。
具体解决方案（非递归）：
非递归需要对二叉树的性质有着深刻的认知。这里先假设两个遍历的值。
前序序列[1,2,4,6,5,3,7,8]，中序序列[6,4,2,5,1,7,3,8]
开始遍历前序序列，此时中序数组下标初始化为0。
当为前序的值为1，需要判断2是左节点还是亲戚节点，此时中序指向的是6。
显然，如果根节点1没有左节点，那么中序序列对应的首位元素也必然是1，所以2只能是左节点。
这里采取和非递归前序遍历类似的做法，设定一个栈s存放前序当前遍历的节点。
当遍历到5的时候，S：1 2 4 6
此时栈顶的值和中序的值相同了，则又需要判断5是6的左节点还是亲戚节点。
而根据中序遍历的性质，6是没有左子节点的，所以5必然是6的某个祖先的右节点。
此时栈中存储的是6本身和6的全部祖先，可以推断出5必然是其中某个节点的右节点。
目前树构成的情况是：
在推理的过程中，可以稍加带入，如果5是6的右节点会怎么样？
显然，根据中序遍历的性质，此时输出的结果应为：6 5 4 2 1
这和所给的序列是明显不符的，但同时也可以观察出一个新的性质：二叉树中任意一个纯左斜的子树，例如上图中的所示，其前序和后序的序列必然是完全相反的！
这时候，S为1 2 4 6，后序数组值为6，与栈顶相同，抛出
这时候，S为1 2 4，后序数组值为4，与栈顶相同，抛出
这时候，S为1 2，后序数组值为2，与栈顶相同，抛出
这时候，S为1，后序数组值为5，与栈顶不同，将刚刚抛出的2拿过来，5就是它的右节点了。
掌握这两种情况后，依次判断前序数组中每个i和i+1元素的关系即可。
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
//前序遍历第一个值必是根节点，直接初始化并入栈
TreeNode root = new TreeNode(preorder[0]);
Deque<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
int j = 0; //中序遍历的下标
for (int i = 1; i < preorder.length; i++) {
int cur = preorder[i];
TreeNode peek = stack.peek();
//如果不同则直接生成左斜子树
if (peek.val != inorder[j]) {
peek.left = new TreeNode(cur);
stack.push(peek.left);
} else { //如果相同则从左斜子树逆序往上寻找该放右子节点的地方
while (!stack.isEmpty() && stack.peek().val == inorder[j]) {
peek = stack.pop();
j++;
}
peek.right = new TreeNode(cur);
stack.push(peek.right);
}
}
return root;
}
}
?