题解 | #重建二叉树#

知识点：前序遍历，中序遍历，二叉树的构造

数据结构课本里使用c++版本写的，这里用java版本仿了一遍

import java.util.*;

public class Solution {

public TreeNode createByPreMid(int[] pre,int[] mid,int ipre,int imid,int n){
    if(n==0)
        return null;
    TreeNode node = new TreeNode(0);
    node.val = pre[ipre];
    int i;
    for(i=0;i<n;++i){
        if(pre[ipre]==mid[imid+i])
            break;
    }
    node.left = createByPreMid(pre,mid,ipre+1,imid,i);
    node.right= createByPreMid(pre,mid,ipre+i+1,imid+i+1,n-i-1);
    return node;
}

public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
    int n = pre.length;
    return createByPreMid(pre,vin,0,0,n);
}

}