输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//使用递归的思想
/**
* 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.length == 0){
return null;
}
TreeNode treeNode = new TreeNode(preorder[0]);
if(preorder.length == 1){
return treeNode;
}
List<Integer> preorderLeftList = new ArrayList<Integer>();
List<Integer> preorderRightList = new ArrayList<Integer>();
List<Integer> inorderLeftList = new ArrayList<Integer>();
List<Integer> inorderRightList = new ArrayList<Integer>();
int inorderLen = inorder.length;
for (int i=0; i<inorderLen; i++){
if(inorder[i] == preorder[0]){
break;
}else{
inorderLeftList.add(inorder[i]);
}
}
for(int j=inorderLeftList.size()+1; j<inorderLen; j++){
inorderRightList.add(inorder[j]);
}
for (int k=1; k<=inorderLeftList.size(); k++){
preorderLeftList.add(preorder[k]);
}
for (int m=inorderLeftList.size()+1; m<preorder.length; m++){
preorderRightList.add(preorder[m]);
}
int[] preLeftArr = new int[preorderLeftList.size()];
int[] inoderLeftArr = new int[inorderLeftList.size()];
int[] preRightArr = new int[preorderRightList.size()];
int[] inoderRightArr = new int[inorderRightList.size()];
preLeftArr = listToInt(preLeftArr,preorderLeftList);
preRightArr = listToInt(preRightArr,preorderRightList);
inoderLeftArr = listToInt(inoderLeftArr,inorderLeftList);
inoderRightArr = listToInt(inoderRightArr,inorderRightList);
TreeNode leftTreeNode = buildTree(preLeftArr,inoderLeftArr);
TreeNode rightTreeNode = buildTree(preRightArr,inoderRightArr);
treeNode.left = leftTreeNode;
treeNode.right = rightTreeNode;
return treeNode;
}
private int[] listToInt(int[] arr, List<Integer> list){
for (int i=0; i<list.size(); i++){
arr[i] = list.get(i);
}
return arr;
}
}
原文：https://www.cnblogs.com/zldmy/p/12393098.html