题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如：前序遍历序列｛ 1, 2, 4, 7, 3, 5, 6, 8｝和中序遍历序列｛4, 7, 2, 1, 5, 3, 8, 6}，重建出下图所示的二叉树并输出它的头节点。
img1.png
这棵树的前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}。
思路分析：要重建一个树，首先要找到它的根节点，然后构建它的左子树，然后构建它的右子树。构建(左、右子树)的过程也是一样的，先构建(左、右子树)的根节点，然后是(左、右子树)的左子树，(左、右子树)的右子树。所以这是一个递归的过程。
如图所示，前序遍历序列的第一个数字1就是根节点的值。扫描中序遍历序列，就能确定根节点的值的位置。根据中序遍历的特点，在根节点的值1前面的3个数字都是左子树节点的值，位于1后面的数字都是右子树节点的值。
在这个例子中，左子树的前序遍历序列就是{2, 4, 7}，中序遍历序列就是{4, 7, 2}。
在这个例子中，右子树的前序遍历序列就是{3, 5, 6, 8}，中序遍历序列就是{5, 3, 8, 6}。
既然我们已经分别找到了左、右子树的前序遍历序列和中序遍历序列，我们可以用同样的方法分别构建左、右子树。也就是说，接下来的事情可以用递归的方式去完成。
public class Test7 {
/**
*
* @param preOrder 二叉树前序遍历的数组
* @param midOrder 二叉树中序遍历的数组
* @return
*/
public static BinaryTreeNode construct(int[] preOrder, int[] midOrder) {
if (preOrder == null || midOrder == null
|| preOrder.length != midOrder.length
|| preOrder.length < 1) {
return null;
}
return construct(preOrder, 0, preOrder.length - 1, midOrder, 0, midOrder.length - 1);
}
/**
* @param preOrder 要重建的树前序遍历的数组
* @param pStart 要重建的树的第一个节点在前序遍历数组中的位置
* @param pEnd 要重建的树的最后一个节点在前序遍历数组中的位置
* @param midOrder 要重建的树中序遍历的数组
* @param mStart 要重建的树的第一个节点在中序遍历数组中的位置
* @param mEnd 要重建的树的最后一个节点在中序遍历数组中的位置
* @return 树的根节点
*/
public static BinaryTreeNode construct(int[] preOrder, int pStart, int pEnd, int[] midOrder, int mStart, int mEnd) {
//开始位置大于结束位置，说明已经没有需要处理的元素了。
if (pStart > pEnd) {
return null;
}
//取前序遍历的第一个数字，就是当前的根节点
int value = preOrder[pStart];
//注释0处
int index = mStart;
//注释1处，在中序遍历中找根节点的位置
while (index <= mEnd && midOrder[index] != value) {
index++;
}
//如果在整个中序遍历的数组中没有找到，说明说入的参数是不合法的，抛出异常
if (index > mEnd) {
throw new IllegalArgumentException("Invalid input");
}
//创建当前的根节点，并为根节点赋值
BinaryTreeNode node = new BinaryTreeNode();
node.value = value;
/**
* 递归构建当前根节点的左子树，左子树的元素个数：index-mStart个
* 左子树对应的前序遍历的位置在[pStart+1, pStart+index-mStart]
* 左子树对应的中序遍历的位置在[mStart, index-1]
*/
//注释2处
node.left = construct(preOrder, pStart + 1, pStart + index - mStart, midOrder, mStart, index - 1);
/**
* 递归构建当前根结点的右子树，右子树的元素个数：mEnd-index个
* 右子树对应的前序遍历的位置在[pStart+index-mStart+1, pEnd]
* 右子树对应的中序遍历的位置在[index+1, mEnd]
*/
//注释3处
node.right = construct(preOrder, pStart + index - mStart + 1, pEnd, midOrder, index + 1, mEnd);
return node;
}
// 前序遍历二叉树
public static void printTree(BinaryTreeNode root) {
if (root != null) {
System.out.print(root.value + " ");
printTree(root.left);
printTree(root.right);
}
}
}
注释2处，3处，构建左右子树的时候，递归调用construct函数的时候，几个参数是怎么来的呢？
注释2处：
//注释2处
node.left = construct(preOrder, pStart + 1, pStart + index - mStart, midOrder, mStart, index - 1);
注释3处
//注释3处
node.right = construct(preOrder, pStart + index - mStart + 1, pEnd, midOrder, index + 1, mEnd);
接下来我们就来析一下第1次调用construct函数的时候:
- 在注释0处，将
mStart赋值给了index，然后在注释1处找到了根节点在中序遍历数组中的位置就是index。那么左子树的节点的个数就是index-mstart个，右子树节点的个数就是mEnd-index个。
在这个例子中：第一次调用的时候，index最终是3，左子树的节点的个数就是index-mstart = 3-0 =3 个。
-
index左边都是左子树的节点，那么左子树的第一个节点在中序遍历数组中的位置是mStart，左子树的最后一个节点在中序遍历数组中的位置是index-1。
-
index右边都是右子树的节点，那么右子树的第一个节点在中序遍历数组中的位置是index+1，左子树的最后一个节点在中序遍历数组中的位置是mEnd。
-
根节点在前序遍历数组的第一个位置就是
pStart，那么左子树在前序遍历数组中的第一个节点的位置就是pStart+1，最后一个节点的位置就是第一个节点的位置加上左子树的节点个数并且减去1，也就是pStart+1 + index- mstart -1=pStart + index - mStart。 -
左子树的最后一个节点在前序遍历数组中的位置是
pStart + index - mStart，前序遍历数组中剩下的都是右子树的节点了，那么右子树的第一个节点在前序遍历数组中的位置就是pStart + index - mStart + 1，右子树的最后一个节点在前序遍历数组中的位置是pEnd。
//main函数和测试用例
public static void main(String[] args) {
test1();
System.out.println();
test2();
System.out.println();
test3();
System.out.println();
test4();
System.out.println();
test5();
System.out.println();
test6();
System.out.println();
test7();
}
// 普通二叉树
// 1
// / \
// 2 3
// / / \
// 4 5 6
// \ /
// 7 8
private static void test1() {
int[] preorder = {1, 2, 4, 7, 3, 5, 6, 8};
int[] inorder = {4, 7, 2, 1, 5, 3, 8, 6};
BinaryTreeNode root = construct(preorder, inorder);
printTree(root);
}
// 所有结点都没有右子结点
// 1
// /
// 2
// /
// 3
// /
// 4
// /
// 5
private static void test2() {
int[] preorder = {1, 2, 3, 4, 5};
int[] inorder = {5, 4, 3, 2, 1};
BinaryTreeNode root = construct(preorder, inorder);
printTree(root);
}
// 所有结点都没有左子结点
// 1
// \
// 2
// \
// 3
// \
// 4
// \
// 5
private static void test3() {
int[] preorder = {1, 2, 3, 4, 5};
int[] inorder = {1, 2, 3, 4, 5};
BinaryTreeNode root = construct(preorder, inorder);
printTree(root);
}
// 树中只有一个结点
private static void test4() {
int[] preorder = {1};
int[] inorder = {1};
BinaryTreeNode root = construct(preorder, inorder);
printTree(root);
}
// 完全二叉树
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
private static void test5() {
int[] preorder = {1, 2, 4, 5, 3, 6, 7};
int[] inorder = {4, 2, 5, 1, 6, 3, 7};
BinaryTreeNode root = construct(preorder, inorder);
printTree(root);
}
// 输入空指针
private static void test6() {
construct(null, null);
}
// 输入的两个序列不匹配
private static void test7() {
int[] preorder = {1, 2, 4, 5, 3, 6, 7};
int[] inorder = {4, 2, 8, 1, 6, 3, 7};
BinaryTreeNode root = construct(preorder, inorder);
printTree(root);
}
}
注意：参考链接【剑指Offer学习】【面试题6 ：重建二叉树】文章中有一个错误的地方。
// 递归构建当前根结点的左子树，左子树的元素个数：index-is+1个
这句注释关于左子树元素的个数是是不对的，正确的应该是：
//递归构建当前根节点的左子树，左子树的元素个数：index-is个。
参考链接：
网友评论