一定要画图,并使用指针标识
import java.util.*;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
if(pre.length == 0 || vin.length == 0){
return null;
}
// 构建根节点
int rootVal = pre[0];
TreeNode root = new TreeNode(rootVal);
// 在中序遍历中找到根节点位置
int rootIndex = 0;
for(int i = 0; i < vin.length; i++){
if(vin[i] == rootVal){
rootIndex = i;
break;
}
}
// 构建左子树
if(rootIndex != 0) {
int[] leftPre = new int[rootIndex];
int[] leftVin = new int[rootIndex];
for(int i = 0; i < rootIndex; i++){
leftPre[i] = pre[i + 1];
leftVin[i] = vin[i];
}
root.left = reConstructBinaryTree(leftPre, leftVin);
}
// 构建右子树
if(rootIndex != vin.length - 1){
int[] rightPre = new int[vin.length - rootIndex - 1];
int[] rightVin = new int[vin.length - rootIndex - 1];
for(int i = 0; i < vin.length - rootIndex - 1; i++){
rightPre[i] = pre[rootIndex + i + 1];
rightVin[i] = vin[rootIndex + i + 1];
}
root.right = reConstructBinaryTree(rightPre, rightVin);
}
return root;
}
}