# 剑指offer 面试题6—重建二叉树

public TreeNode constructionOfTree(int[] pre, int[] in) {
if (pre == null || pre.length == 0 || in == null || in.length == 0) {
return null;
}

if (pre.length == 1 && in.length == 1) {
return new TreeNode(pre[0]);
}

int len = pre.length;
int root = pre[0];
TreeNode tree = new TreeNode(root);

int del = -1;
for (int i = 0; i < in.length; i++) {
if (in[i] == root) {
del = i;
break;
}
}

int right_length = in.length - del - 1;
int[] left_pre = new int[del];
int[] left_in = new int[del];
int[] right_pre = new int[right_length];
int[] right_in = new int[right_length];

for (int i = 1; i < del + 1; i++) {
left_pre[i - 1] = pre[i];
left_in[i - 1] = in[i - 1];
}

for (int i = del + 1; i < pre.length; i++) {
right_pre[i - del - 1] = pre[i];
right_in[i - del - 1] = in[i];
}

tree.left = constructionOfTree(left_pre, left_in);
tree.right = constructionOfTree(right_pre, right_in);

return tree;
}

/**
*
* @param preOrder 前序遍历数组
* @param inOrder 中序遍历数组
* @param length 数组长度
* @return 根结点
*/
public static BinaryTreeNode Construct(int[] preOrder, int[] inOrder,int length){
if (preOrder == null || inOrder == null || length <= 0) {
return null;
}
try {
return ConstructCore(preOrder, 0, preOrder.length - 1, inOrder, 0,inOrder.length - 1);
} catch (InvalidPutException e) {
e.printStackTrace();
return null;
}
}

/**
*
* @param PreOrder
*            前序遍历序列
* @param startPreIndex
*            前序序列开始位置
* @param endPreIndex
*            前序序列结束位置
* @param InOrder
*            中序遍历序列
* @param startInIndex
*            中序序列开始位置
* @param endInIndex
*            中序序列结束位置
* @return 根结点
* @throws InvalidPutException
*/
public static BinaryTreeNode ConstructCore(int[] preOrder,int startPreIndex, int endPreIndex,
int[] inOrder,int startInIndex, int endInIndex) throws InvalidPutException {

int rootValue = preOrder[startPreIndex];
System.out.println("rootValue = " + rootValue);
BinaryTreeNode root = new BinaryTreeNode(rootValue);

// 只有一个元素
if (startPreIndex == endPreIndex) {
if (startInIndex == endInIndex
&& preOrder[startPreIndex] == inOrder[startInIndex]) {
System.out.println("only one element");
return root;
} else {
throw new InvalidPutException();
}
}

// 在中序遍历中找到根结点的索引
int rootInIndex = startInIndex;

while (rootInIndex <= endInIndex && inOrder[rootInIndex] != rootValue) {
++rootInIndex;
}

if (rootInIndex == endInIndex && inOrder[rootInIndex] != rootValue) {
throw new InvalidPutException();

}

int leftLength = rootInIndex - startInIndex;

int leftPreOrderEndIndex = startPreIndex + leftLength;

if (leftLength > 0) {
// 构建左子树
root.leftNode = ConstructCore(preOrder, startPreIndex + 1,
leftPreOrderEndIndex, inOrder, startInIndex,
rootInIndex - 1);
}

if (leftLength < endPreIndex - startPreIndex) {
// 右子树有元素,构建右子树
root.rightNode = ConstructCore(preOrder, leftPreOrderEndIndex + 1,
endPreIndex, inOrder, rootInIndex + 1, endInIndex);
}
return root;
}

static class InvalidPutException extends Exception {

private static final long serialVersionUID = 1L;

}

public static void printPreOrder(BinaryTreeNode root) {
if (root == null) {
return;
} else {
System.out.print(root.value + " ");
}

if (root.leftNode != null) {
printPreOrder(root.leftNode);
}

if (root.rightNode != null) {
printPreOrder(root.rightNode);
}
}

public static void main(String[] args) throws Exception{
ConstructionOfTree test=new ConstructionOfTree();
int[] preOrder={1,2,4,7,3,5,6,8};
int[] inOrder={4,7,2,1,5,3,8,6};
printPreOrder(test.Construct(preOrder, inOrder, preOrder.length));
}  

### BinaryTreeNode.java

public class BinaryTreeNode {
public int value;
public BinaryTreeNode leftNode;
public BinaryTreeNode rightNode;

public BinaryTreeNode() {

}

public BinaryTreeNode(int value) {
this.value = value;
this.leftNode = null;
this.rightNode = null;
}
}

|
2月前
【一刷《剑指Offer》】面试题 23：从上往下打印二叉树
【一刷《剑指Offer》】面试题 23：从上往下打印二叉树
37 0
|
2月前
【一刷《剑指Offer》】面试题 22：栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22：栈的压入、弹出系列
28 0
|
2月前
|

【一刷《剑指Offer》】面试题 21：包含 main 函数的栈
【一刷《剑指Offer》】面试题 21：包含 main 函数的栈
14 0
|
2月前
【一刷《剑指Offer》】面试题 20：顺时针打印矩阵
【一刷《剑指Offer》】面试题 20：顺时针打印矩阵
39 0
|
2月前
【一刷《剑指Offer》】面试题 19：二叉树的镜像
【一刷《剑指Offer》】面试题 19：二叉树的镜像
24 0
|
2月前
【一刷《剑指Offer》】面试题 18：树的子结构
【一刷《剑指Offer》】面试题 18：树的子结构
29 0
|
2月前
【一刷《剑指Offer》】面试题 17：合并两个排序的链表
【一刷《剑指Offer》】面试题 17：合并两个排序的链表
26 0
|
2月前
【一刷《剑指Offer》】面试题 16：反转链表
【一刷《剑指Offer》】面试题 16：反转链表
31 0
|
2月前
【一刷《剑指Offer》】面试题 15：链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15：链表中倒数第 k 个结点
27 0
|
2月前
|
C++
【一刷《剑指Offer》】面试题 14：调整数组顺序使奇数位于偶数前面
【一刷《剑指Offer》】面试题 14：调整数组顺序使奇数位于偶数前面
28 0