剑指Offer面试题：5.重建二叉树
剑指Offer面试题：5.重建二叉树
Edison Zhou
发布于 2018-08-20 16:26:27
发布于 2018-08-20 16:26:27
一、题目：重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示的二叉树并输出它的头结点。
二、解题思路
在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列，才能找到根结点的值。
前序遍历序列的第一个数字1就是根结点的值。扫描中序遍历序列，就能确定根结点的值的位置。根据中序遍历特点，在根结点的值1前面的3个数字都是左子树结点的值，位于1后面的数字都是右子树结点的值。
在二叉树的前序遍历和中序遍历的序列中确定根结点的值、左子树结点的值和右子树结点的值的步骤如下图所示：
分别找到了左、右子树的前序遍历序列和中序遍历序列，我们就可以用同样的方法分别去构建左右子树。换句话说，这是一个递归的过程。
思路总结：先根据前序遍历序列的第一个数字创建根结点，接下来在中序遍历序列中找到根结点的位置，这样就能确定左、右子树结点的数量。在前序遍历和中序遍历的序列中划分了左、右子树结点的值之后，就可以递归地去分别构建它的左右子树。
三、解决问题
3.1 代码实现
public static Node<int> Construct(int[] preOrder, int[] inOrder, int length)
{
// 空指针判断
if (preOrder == null || inOrder == null || length <= 0)
{
return null;
}
return ConstructCore(preOrder, 0, preOrder.Length - 1, inOrder, 0, inOrder.Length - 1);
}
public static Node<int> ConstructCore(int[] preOrder, int startPreOrder, int endPreOrder, int[] inOrder, int startInOrder, int endInOrder)
{
// 前序遍历序列的第一个数字是根结点的值
int rootValue = preOrder[startPreOrder];
Node<int> root = new Node<int>();
root.data = rootValue;
root.lchild = root.rchild = null;
if (startPreOrder == endPreOrder)
{
if (startInOrder == endInOrder &&
preOrder[startPreOrder] == inOrder[startInOrder])
{
return root;
}
else
{
throw new Exception("Invalid input!");
}
}
// 在中序遍历中找到根结点的值
int rootInOrder = startInOrder;
while (rootInOrder <= endInOrder && inOrder[rootInOrder] != rootValue)
{
rootInOrder++;
}
// 输入的两个序列不匹配的情况
if (rootInOrder == endInOrder && inOrder[rootInOrder] != rootValue)
{
throw new Exception("Invalid input!");
}
int leftLength = rootInOrder - startInOrder;
int leftPreOrderEnd = startPreOrder + leftLength;
if (leftLength > 0)
{
// 构建左子树
root.lchild = ConstructCore(preOrder, startPreOrder + 1, leftPreOrderEnd, inOrder, startInOrder, rootInOrder - 1);
}
if (leftLength < endPreOrder - startPreOrder)
{
// 构建右子树
root.rchild = ConstructCore(preOrder, leftPreOrderEnd + 1, endPreOrder, inOrder, rootInOrder + 1, endInOrder);
}
return root;
}3.2 单元测试
首先封装了一个测试主入口，方法定义如下：
// 单元测试主入口
public static void ConstructTestPortal(string testName, int[] preOrder, int[] inOrder, int length)
{
if (!string.IsNullOrEmpty(testName))
{
Console.WriteLine("{0} begins:", testName);
}
// 打印先序遍历
Console.Write("The preorder sequence is : ");
for (int i = 0; i < length; i++)
{
Console.Write(preOrder[i]);
}
Console.Write("\n");
// 打印中序遍历
Console.Write("The inorder sequence is : ");
for (int i = 0; i < length; i++)
{
Console.Write(inOrder[i]);
}
Console.Write("\n");
try
{
Node<int> root = Construct(preOrder, inOrder, length);
BinaryTree<int> bTree = new BinaryTree<int>();
bTree.Root = root;
Console.Write("The binary tree is : ");
// 重建的二叉树层次遍历
bTree.LevelOrder(bTree.Root);
if (!string.IsNullOrEmpty(testName))
{
Console.Write("\n{0} end\n\n", testName);
}
}
catch (Exception)
{
Console.WriteLine("Invalid input!");
}
}该方法首先接收参数，依次打印先序遍历和中序遍历，最后通过调用Construct方法获得重建的二叉树的根节点，并实例化一个二叉树的数据结构（本处的二叉树结构的实现请阅读《数据结构基础温故-4.树与二叉树（上）》），最后输出重建后的二叉树的层次遍历验证是否重建成功。
（1）普通二叉树
// 普通二叉树
// 1
// / \
// 2 3
// / / \
// 4 5 6
// \ /
// 7 8
public static void ConstructTest1()
{
int[] preorder = { 1, 2, 4, 7, 3, 5, 6, 8 };
int[] inorder = { 4, 7, 2, 1, 5, 3, 8, 6 };
ConstructTestPortal("ConstructTest1", preorder, inorder, 8);
}（2）所有结点都没有右子结点
// 所有结点都没有右子结点
// 1
// /
// 2
// /
// 3
// /
// 4
// /
// 5
public static void ConstructTest2()
{
int[] preorder = { 1, 2, 3, 4, 5 };
int[] inorder = { 5, 4, 3, 2, 1 };
ConstructTestPortal("ConstructTest2", preorder, inorder, 5);
}（3）所有结点都没有左子结点
// 所有结点都没有左子结点
// 1
// \
// 2
// \
// 3
// \
// 4
// \
// 5
public static void ConstructTest3()
{
int[] preorder = {1, 2, 3, 4, 5};
int[] inorder = {1, 2, 3, 4, 5};
ConstructTestPortal("ConstructTest3", preorder, inorder, 5);
}（4）树中只有一个结点
// 树中只有一个结点
public static void ConstructTest4()
{
int[] preorder = { 1 };
int[] inorder = { 1 };
ConstructTestPortal("ConstructTest4", preorder, inorder, 1);
}（5）完全二叉树
// 完全二叉树
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
public static void ConstructTest5()
{
int[] preorder = {1, 2, 4, 5, 3, 6, 7};
int[] inorder = {4, 2, 5, 1, 6, 3, 7};
ConstructTestPortal("ConstructTest5", preorder, inorder, 7);
}（6）输入空指针
// 输入空指针
public static void ConstructTest6()
{
ConstructTestPortal("ConstructTest6", null, null, 0);
}（7）输入的两个序列不匹配
// 输入的两个序列不匹配
public static void ConstructTest7()
{
int[] preorder = {1, 2, 4, 5, 3, 6, 7};
int[] inorder = {4, 2, 8, 1, 6, 3, 7};
ConstructTestPortal("ConstructTest7", preorder, inorder, 7);
}单元测试的结果如下图所示：
作者：周旭龙
出处：http://edisonchou.cnblogs.com
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文链接。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-08-19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录