题解 | #重建二叉树#

中序和前序或后序，唯一确定一个二叉树

以中序和前序举例，前序[1,2,4,7,3,5,6,8],中序[4,7,2,1,5,3,8,6]

前序遍历规律-根左右可知，第一个数一定是此树的根节点即“1”，又中序遍历规律-左根右，所以找到“1”在中序中的索引，就可以一分为二，左子树中序和右子树中序，基于中序中根节点的索引，同样也可以将前序一分为二

根节点 1

左子树 前序 [2,4,7] ，中序 [4,7,2]

右子树 前序 [3,5,6,8]，中序[5,3,8,6]

递归此步骤即可以建立二叉树

public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
    return partition(pre, 0, pre.length, vin, 0, vin.length);
}

public TreeNode partition(int[] pre, int preleft, int preright, int[] vin, int vinleft, int vinright){//左闭右开，很重要，循环不变量
    if(preleft == preright || vinleft == vinright) return null;
    
    int rootval = pre[preleft];
    TreeNode root = new TreeNode(rootval);
    
    int index = -1;
    
    for(int i = vinleft; i < vinright; i++){//寻找中序总，根节点索引
        if(vin[i] == rootval){
            index = i;
            break;
        }
    }
    
    //以下就是分割为左子树和右子树，tips,一个二叉树，中序和前序的长度一定相等
    int leftvin = vinleft;
    int rightvin = index;
    
    int leftpre = preleft + 1;
    int rightpre = rightvin - leftvin + leftpre;
    
    TreeNode left = partition(pre, leftpre, rightpre, vin, leftvin, rightvin);
    root.left = left;
    
    leftvin = index + 1;
    rightvin = vinright;
    
    rightpre = preright;
    leftpre = rightpre - (rightvin - leftvin);
    
    TreeNode right = partition(pre, leftpre, rightpre, vin, leftvin, rightvin);
    root.right = right;
    
    return root;
}
}