题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字，例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出二叉树并输出它的头结点。
利用递归的方法构建，其实没有想象的那么难，主要是理解构建过程就行！！
测试用例：
1）普通二叉树（完全二叉树，不完全二叉树）
2）特殊二叉树（所有结点都没有右子结点的二叉树，所有结点都没有左子节点的二叉树，只有一个结点的二叉树）
3）特殊输入测试（二叉树的根结点指针为null，输入的前序遍历序列和中序遍历序列不匹配）
树的类：
package com.yyq;
/**
* Created by Administrator on 2015/9/8.
*/
public class BinaryTreeNode {
int m_nValue;
BinaryTreeNode m_pLeft;
BinaryTreeNode m_pRight; public BinaryTreeNode(int m_nValue){
this.m_nValue = m_nValue;
} public BinaryTreeNode getM_pRight() {
return m_pRight;
} public void setM_pRight(BinaryTreeNode m_pRight) {
this.m_pRight = m_pRight;
} public BinaryTreeNode getM_pLeft() {
return m_pLeft;
} public void setM_pLeft(BinaryTreeNode m_pLeft) {
this.m_pLeft = m_pLeft;
} public int getM_nValue() {
return m_nValue;
} public void setM_nValue(int m_nValue) {
this.m_nValue = m_nValue;
}
}
实现类：
package com.yyq; import java.util.Arrays; /**
* Created by Administrator on 2015/9/8.
*/
public class Construct { public static BinaryTreeNode reConstruct(int[] preOrder, int[] inOrder) {
if (preOrder == null || inOrder == null) {
return null;
}
int rootData = preOrder[0];// 前序遍历第一个节点是子节点
BinaryTreeNode root = new BinaryTreeNode(rootData);// 找到跟节点
root.m_pLeft = root.m_pRight = null; //只有一个数字的情况
if (preOrder.length == 1 && inOrder.length == 1) {
if (preOrder[0] == inOrder[0]) {
return root;
} else {
throw new IllegalArgumentException("invalid input");
}
} // 在中序遍历中找到rootData的位置
int rootinIndex = 0;
while (rootinIndex < inOrder.length && rootData != inOrder[rootinIndex]) {
rootinIndex++;
}
if (rootinIndex == inOrder.length && rootData != inOrder[rootinIndex - 1]) {
throw new IllegalArgumentException("invalid input");
} // 有左孩子节点
if (rootinIndex > 0) {
root.m_pLeft = reConstruct(
Arrays.copyOfRange(preOrder, 1, rootinIndex + 1),
Arrays.copyOfRange(inOrder, 0, rootinIndex)); //注意复制从0到rootinIndex，但是不包括rootinIndex
}
// 有右孩子节点
if (rootinIndex < inOrder.length - 1) {
root.m_pRight = reConstruct(
Arrays.copyOfRange(preOrder, rootinIndex + 1, preOrder.length),
Arrays.copyOfRange(inOrder, rootinIndex + 1, inOrder.length));
}
return root;
} // ====================测试代码====================
public static void Test(String testName, int[] preorder, int[] inorder) {
if (testName != null || testName != " ")
System.out.println(testName + " begins:");
if (preorder == null || inorder == null){
return ;
}
System.out.println("The preorder sequence is: ");
int prelen = preorder.length;
for (int i = 0; i < prelen; ++i)
System.out.print(preorder[i] + " ");
System.out.println(); System.out.println("The inorder sequence is: ");
int inlen = inorder.length;
for (int i = 0; i < inlen; ++i)
System.out.print(inorder[i] + " ");
System.out.println(); try {
BinaryTreeNode root = reConstruct(preorder, inorder);
} catch (Exception e) {
e.printStackTrace();
}
} // 普通二叉树
// 1
// / \
// 2 3
// / / \
// 4 5 6
// \ /
// 7 8
void Test1() {
int preorder[]={1, 2, 4, 7, 3, 5, 6, 8};
int inorder[]={4, 7, 2, 1, 5, 3, 8, 6};
Test("Test1", preorder, inorder);
} // 所有结点都没有右子结点
// 1
// /
// 2
// /
// 3
// /
// 4
// /
//
void Test2() {
int preorder[]={1, 2, 3, 4, 5} ;
int inorder[]={5, 4, 3, 2, 1} ;
Test("Test2", preorder, inorder);
} // 所有结点都没有左子结点
// 1
// \
// 2
// \
// 3
// \
// 4
// \
// 5
void Test3() {
int preorder[]={1, 2, 3, 4, 5} ;
int inorder[]={1, 2, 3, 4, 5} ;
Test("Test3", preorder, inorder);
} // 树中只有一个结点
void Test4() {
int preorder[]={1} ;
int inorder[]={1} ;
Test("Test4", preorder, inorder);
} // 完全二叉树
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
void Test5() {
int preorder[]={1, 2, 4, 5, 3, 6, 7} ;
int inorder[]={4, 2, 5, 1, 6, 3, 7} ;
Test("Test5", preorder, inorder);
} // 输入空指针
void Test6() {
Test("Test6", null, null);
} // 输入的两个序列不匹配
void Test7() {
int preorder[]={1, 2, 4, 5, 3, 6, 7} ;
int inorder[]={4, 2, 8, 1, 6, 3, 7} ;
Test("Test7: for unmatched input", preorder, inorder);
} public static void main(String[] args) {
{
Construct construct = new Construct();
construct.Test1();
construct.Test2();
construct.Test3();
construct.Test4();
construct.Test5();
construct.Test6();
construct.Test7();
}
}
}
输出结果：
Test1 begins:
The preorder sequence is:
1 2 4 7 3 5 6 8
The inorder sequence is:
4 7 2 1 5 3 8 6
Test2 begins:
The preorder sequence is:
1 2 3 4 5
The inorder sequence is:
5 4 3 2 1
Test3 begins:
The preorder sequence is:
1 2 3 4 5
The inorder sequence is:
1 2 3 4 5
Test4 begins:
The preorder sequence is:
1
The inorder sequence is:
1
Test5 begins:
The preorder sequence is:
1 2 4 5 3 6 7
The inorder sequence is:
4 2 5 1 6 3 7
Test6 begins:
Test7: for unmatched input begins:
The preorder sequence is:
1 2 4 5 3 6 7
The inorder sequence is:
4 2 8 1 6 3 7
java.lang.IllegalArgumentException: invalid input
at com.yyq.Construct.reConstruct(Construct.java:23)
at com.yyq.Construct.reConstruct(Construct.java:44)
at com.yyq.Construct.reConstruct(Construct.java:38)
at com.yyq.Construct.Test(Construct.java:71)
at com.yyq.Construct.Test7(Construct.java:151)
at com.yyq.Construct.main(Construct.java:163)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:483)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:140)
Process finished with exit code 0