输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
分析：递归构建二叉树
根据中序遍历和前序遍历可以确定二叉树，具体过程为：
- 根据前序序列第一个结点确定根结点
- 根据根结点在中序序列中的位置分割出左右两个子序列
- 对左子树和右子树分别递归使用同样的方法继续分解
例如：
前序序列{1,2,4,7,3,5,6,8} = pre
中序序列{4,7,2,1,5,3,8,6} = in
- 根据当前前序序列的第一个结点确定根结点，为 1
- 找到 1 在中序遍历序列中的位置，为 in[3]
- 切割左右子树，则 in[3] 前面的为左子树， in[3] 后面的为右子树
- 则切割后的左子树前序序列为：{2,4,7}，切割后的左子树中序序列为：{4,7,2}；切割后的右子树前序序列为：{3,5,6,8}，切割后的右子树中序序列为：{5,3,8,6}
- 对子树分别使用同样的方法分解
法一：
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.Arrays;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if (pre.length == 0 || in.length == 0) {
return null;
}
TreeNode root = new TreeNode(pre[0]);
for (int i = 0; i < in.length; i++) {
if(in[i] == pre[0]){
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
break;
}
}
return root;
}
}
法二：
递归方法的基准情形有两个：判断前序遍历的下标范围的开始和结束，若开始大于结束，则当前的二叉树中没有节点，返回空值 null。若开始等于结束，则当前的二叉树中恰好有一个节点，根据节点值创建该节点作为根节点并返回。
若开始小于结束，则当前的二叉树中有多个节点。在中序遍历中得到根节点的位置，从而得到左子树和右子树各自的下标范围和节点数量，知道节点数量后，在前序遍历中即可得到左子树和右子树各自的下标范围，然后递归重建左子树和右子树，并将左右子树的根节点分别作为当前根节点的左右子节点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || preorder.length == 0){
return null;
}
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i], i);
}
TreeNode root = reBuildTree(preorder, 0 , preorder.length - 1, inorder, 0, inorder.length - 1, map);
return root;
}
public TreeNode reBuildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer,Integer> map){
if(preStart > preEnd){
return null;
}
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
if(preStart == preEnd){
return root;
}else{
int rootIndex = map.get(rootVal);
int leftNum = rootIndex - inStart;
int rightNum = inEnd - rootIndex;
TreeNode left = reBuildTree(preorder, preStart + 1, preStart + leftNum, inorder, inStart, rootIndex - 1, map);
TreeNode right = reBuildTree(preorder, preEnd - rightNum + 1, preEnd, inorder, rootIndex + 1, inEnd, map);
root.left = left;
root.right = right;
return root;
}
}
}
法三：迭代
根据上述例子和分析，可以使用栈保存遍历过的节点。初始时令中序遍历的指针指向第一个元素，遍历前序遍历的数组，如果前序遍历的元素不等于中序遍历的指针指向的元素，则前序遍历的元素为上一个节点的左子节点。如果前序遍历的元素等于中序遍历的指针指向的元素，则正向遍历中序遍历的元素同时反向遍历前序遍历的元素，找到最后一次相等的元素，将前序遍历的下一个节点作为最后一次相等的元素的右子节点。其中，反向遍历前序遍历的元素可通过栈的弹出元素实现。
使用前序遍历的第一个元素创建根节点。
创建一个栈，将根节点压入栈内。
初始化中序遍历下标为 0。
遍历前序遍历的每个元素，判断其上一个元素（即栈顶元素）是否等于中序遍历下标指向的元素。
若上一个元素不等于中序遍历下标指向的元素，则将当前元素作为其上一个元素的左子节点，并将当前元素压入栈内。
若上一个元素等于中序遍历下标指向的元素，则从栈内弹出一个元素，同时令中序遍历下标指向下一个元素，之后继续判断栈顶元素是否等于中序遍历下标指向的元素，若相等则重复该操作，直至栈为空或者元素不相等。然后令当前元素为最后一个想等元素的右节点。
遍历结束，返回根节点。
前序遍历，从根节点root开始，只要有左子节点，就一直会往左下方走，直到最左下角。 而中序遍历，是从最左下角往上（示例中的4-5-8-9-3），如果碰到节点有右子节点，则会转向（示例中的8-10）。
因此，代码中的if块是用前序数组一直构建左子树，如果碰到了inorder[inorderIndex]，表示到了左下角，这时就需要往上走并处理右子树，也就是while代码块。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || preorder.length == 0){
return null;
}
TreeNode root = new TreeNode(preorder[0]);
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
int inIndex = 0;
for(int i = 1; i < preorder.length; i++){
int preorderVal = preorder[i];
TreeNode node = stack.peek();
if(node.val != inorder[inIndex]){
node.left = new TreeNode(preorderVal);
stack.push(node.left);
}else{
while(!stack.isEmpty() && stack.peek().val == inorder[inIndex]){
node = stack.pop();
inIndex++;
}
node.right = new TreeNode(preorderVal);
stack.push(node.right);
}
}
return root;
}
}
