题目：根据二叉树的前序和中序遍历结果，还原这颗二叉树。
?
例如，一颗的二叉树如下所示，
=======二叉树=======
? ? ? ?1
?
? ? ?2 ? 3
?
? ?4 5 ?6 7
?
? 8?
=======二叉树=======
?
根据二叉树的遍历策略：
前序遍历策略：1）访问根节点；2）访问左子树；3）访问右子树。
中序遍历策略：1）访问左子树；2）访问根节点；3）访问右子树。
得到前序和中序遍历的结果如下，
前序遍历为：12485367，
中序遍历为：84251637。
?
现在，已知，二叉树的前序遍历结果、中序遍历的结果，求原二叉树。
?
分析：
1. 数据结构
需要定义Node节点，Node节点包含值/键 key，和指向左右子树的引用left、right。前序中序的遍历结果，存储在数组中。
2. 策略
选择递归策略解题，能用递归解题的原因在于，原问题，经过一趟的处理/划分后，能变成一个规模更小的子问题。每一趟处理，得到一个节点Node，通过把子问题处理结果subNode返回给父问题得到的Node的left、right，把父子问题的Node关联起来，最终得到连通的原二叉树。
3. 编程语言
各种编程语言都可以，我用的是Java。
?
/**
* @author tanliwei
* @email tanliweii@qq.com
* @time 2016-4-28下午10:15:32
*/
public class RestoreBinaryTreeByTwoTraverseOder {
//
// ===binary tree===
// 1
//
// 2 3
//
// 4 5 6 7
//
// 8
// ===binary tree===
//
// preorder traversal: 12485367; inorder traversal : 84251637;
//
// input : Preoder & inoder traversal results of a binary tree(e.g. above)
// output : The orginal binary tree
//
public Node restore(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) {
return null;
}
Node root = new Node(preorder[0]);
int rootIndexInInorder = findIndexByValue(preorder[0], inorder);
int lengthOfSubPreorder1 = rootIndexInInorder;
int[] subPreorder1 = {};
if (lengthOfSubPreorder1 > 0) {
// generate subPreorder1 2485
subPreorder1 = new int[lengthOfSubPreorder1];
System
.arraycopy(preorder, 1, subPreorder1, 0,
lengthOfSubPreorder1);
}
// remain subPreorder
int lengthOfSubPreorder2 = preorder.length - lengthOfSubPreorder1 - 1;
int[] subPreorder2 = {};
if (lengthOfSubPreorder2 > 0) {
// generate subPreorder2 367
subPreorder2 = new int[lengthOfSubPreorder2];
System.arraycopy(preorder, preorder.length
- lengthOfSubPreorder2, subPreorder2, 0, lengthOfSubPreorder2);
}
int lengthOfSubinorder1 = rootIndexInInorder;
int[] subinorder1 = {};
if (lengthOfSubinorder1 > 0) {
subinorder1 = new int[lengthOfSubinorder1];
// generate subPreorder1 8425
System.arraycopy(inorder, 0, subinorder1, 0, lengthOfSubinorder1);
}
// remain subInorder
int lengthOfSubInorder2 = preorder.length - lengthOfSubinorder1 - 1;
int[] subinorder2 = {};
if (lengthOfSubInorder2 > 0) {
subinorder2 = new int[lengthOfSubInorder2];
// generate subPreorder2 637
System.arraycopy(inorder, inorder.length
- lengthOfSubInorder2, subinorder2, 0, lengthOfSubPreorder2);
}
root.setLeft(restore(subPreorder1,subinorder1));
root.setRight(restore(subPreorder2,subinorder2));
return root;
}
/**
* find the index of the same value of compareValue in array a
*
* @param compareValue
* @param a
* @return
*/
public int findIndexByValue(int compareValue, int[] a) {
if (null == a || a.length == 0) {
return -1;
}
for (int i = 0; i < a.length; i++) {
if (a[i] == compareValue) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
//12485367; inorder traversal : 84251637;
int[] preorder = {1,2,4,8,5,3,6,7};
int[] inorder = {8,4,2,5,1,6,3,7};
RestoreBinaryTreeByTwoTraverseOder runner = new RestoreBinaryTreeByTwoTraverseOder();
Node head = new Node(-1);//
head = runner.restore(preorder, inorder);
if(null == head){
return ;
}
runner.preorderTraverse(head);
System.out.println();
runner.inorderTraverse(head);
}
/**
* Traverse in preorder
* @param root
*/
public void preorderTraverse(Node root){
if(null == root)
return;
System.out.print(root.getKey());
preorderTraverse(root.getLeft());
preorderTraverse(root.getRight());
}
/**
* Traverse in inorder
* @param root
*/
public void inorderTraverse(Node root){
if(null == root)
return;
inorderTraverse(root.getLeft());
System.out.print(root.getKey());
inorderTraverse(root.getRight());
}
}
class Node {
public Node() {
};
public Node(int key) {
this.key = key;
}
private int key;
private Node left;
private Node right;
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
}
?
代码如上，运行测试可行，尚未进行更多的验证。如有遗漏，欢迎指正。
该问题可以继续拓展为，已知中序、后序遍历结果，还原原二叉树，等等。
原文：http://tanliwei.iteye.com/blog/2294962