【剑指offer】面试题六：重建二叉树

题目：输入某二叉树的前序遍历和中序遍历的结点，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含有重复的数字。假设输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示的二叉树并输出它的头结点。

二叉树结点的定义如下：

typedef struct Node
{
    int m_nValue;
    struct Node* n_pLeft;
    struct Node* m_pRIght 
}BinaryTreeNode, *PBinaryTreeNode;

重建的结果如下图所示：

分析：

在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。但在中序遍历序列中。根结点的值在序列的中间，左子树的所有结点的值位于根结点的值的左边，而右子树的所有结点的值位于根结点的值的右边。因此我们可以得出如下一般的步骤：
1、扫描前序遍历的第一个值（假设为value），找到value在其中序遍历中的位置；
2、通过步骤 1，可知该二叉树的根结点和根结点的左子树与右子树；
3、让左子树与右子树分别重复步骤 1；
4、直到左右子树全部遍历完，便可得到该二叉树。

我们可以分析题目中给出的示例：

1、全部结点的前序遍历序列和中序遍历序列：
　前序序列：{1,2,4,7,3,5,6,8}

　中序序列：{4,7,2,1,5,3,8,6}

　前序遍历的第一个数字 1 就是根结点的值。然后扫描中序遍历，就能确定根结点的值的位置。根据中序遍历的特点，在根结点的值 1 前面的三个数字 4,、7、2 都是左子树结点的值，位于 1 后面的数字 5,3,8,6 都是右子树结点的值。

2、根结点左子树的前序遍历序列和中序遍历序列：

　前序序列：{2,4,7}

　中序序列：{4,7,2}

　由于前序遍历的第一个数字就是左子树的根结点的值，即为 2。从而遍历左子树的中序序列找到 2 的位置，而在中序序列中位于 2 左边的就是根结点左子树的左子树，位于 2 右边的就是根结点左子树的右子树。由中序序列{4,7,2}可知，该子树只有左子树，没有右子树。

3、根结点右子树的前序遍历序列和中序遍历序列：

　前序序列：{3,5,6,8}

　中序序列：{5,3,8,6}

　步骤与2类似，不在赘述。

经过分析可知，既然我们已经分别找到了左、右子树的前序遍历序列和中序遍历序列，我们可以用同样的方法分别取构建左右子树。也就是说，接下来的事情可以用递归的方法去完成。

在分析清楚之后，我们可以用递归的方式去实现该题，代码如下：

  1 // construct.cpp
  2 #include "stdio.h"
  3 #include "stdlib.h"
  4 #include <stdexcept>
  5 
  6 typedef struct Node
  7 {
  8     int m_nValue;
  9     struct Node *m_pLeft;
 10     struct Node *m_pRight;
 11 }BTreeNode, *pBTreeNode;
 12 
 13 BTreeNode *constructCore(int *preOrderStart, int *preOrderEnd,
 14     int *inOrderStart, int *inOrderEnd);
 15 
 16 BTreeNode *construct(int *preOrder, int *inOrder, int len)
 17 {
 18     if(preOrder == NULL || inOrder == NULL || len <= 0)
 19         return NULL;
 20 
 21     return constructCore(preOrder, preOrder + len - 1,
 22             inOrder, inOrder + len - 1);
 23 }
 24 
 25 // 建树 (前序开始、前序结束、中序开始、中序结束)
 26 BTreeNode *constructCore(int *preOrderStart, int *preOrderEnd,
 27     int *inOrderStart, int *inOrderEnd)
 28 {
 29     int rootVal = preOrderStart[0];
 30 
 31     BTreeNode *root = (BTreeNode*)malloc(sizeof(BTreeNode));
 32     root->m_nValue = rootVal;
 33     root->m_pLeft = root->m_pRight = NULL;
 34 
 35     // 递归结束的条件
 36     if(preOrderStart == preOrderEnd)
 37     {
 38         if(inOrderStart == inOrderEnd && *preOrderStart == rootVal)
 39             return root;
 40         else
 41             throw std::out_of_range("Invalid Input");
 42     }
 43 
 44     // 遍历中序序列
 45     int *rootInOrder = inOrderStart;
 46     while(rootInOrder < inOrderEnd && *rootInOrder != rootVal)
 47         ++rootInOrder;
 48 
 49     if(rootInOrder == inOrderEnd && *rootInOrder != rootVal)
 50         throw std::out_of_range("Invalid Input");
 51 
 52     int leftLen = rootInOrder - inOrderStart;
 53     int *leftPreOrderEnd = preOrderStart + leftLen;
 54 
 55     if(leftLen > 0) // 存在左子树
 56     {
 57         // 构建左子树
 58         root->m_pLeft = constructCore(preOrderStart + 1, leftPreOrderEnd,
 59             inOrderStart, rootInOrder - 1);
 60     }
 61     if(leftLen < preOrderEnd - preOrderStart) // 存在右子树
 62     {
 63         // 构建右子树
 64         root->m_pRight = constructCore(leftPreOrderEnd + 1, preOrderEnd,
 65             rootInOrder + 1, inOrderEnd);
 66     }
 67     return root;
 68 }
 69 
 70 void preOrderTr(BTreeNode *root) // 先序遍历
 71 {
 72     if(root != NULL)
 73     {
 74         printf("%2d", root->m_nValue);
 75         preOrderTr(root->m_pLeft);
 76         preOrderTr(root->m_pRight);
 77     }
 78 }
 79 
 80 void inOrderTr(BTreeNode *root) // 中序遍历
 81 {
 82     if(root != NULL)
 83     {
 84         inOrderTr(root->m_pLeft);
 85         printf("%2d", root->m_nValue);
 86         inOrderTr(root->m_pRight);
 87     }
 88 }
 89 
 90 void postOrderTr(BTreeNode *root) // 后序遍历
 91 {
 92     if(root != NULL)
 93     {
 94         postOrderTr(root->m_pLeft);
 95         postOrderTr(root->m_pRight);
 96         printf("%2d", root->m_nValue);
 97     }
 98 }
 99 
100 int main(int argc, char *argv[])
101 {
102     BTreeNode *root = NULL;
103 
104     int preOrder[] = {1, 2, 4, 7, 3, 5, 6, 8};
105     int inOrder[] = {4, 7, 2, 1, 5, 3, 8, 6}; 
106 
107     root = construct(preOrder, inOrder, 8);
108     printf("root value: %d
", root->m_nValue);
109 
110     printf("先序遍历序列
");
111     preOrderTr(root);
112 
113     printf("
中序遍历序列
");
114     inOrderTr(root);
115 
116     printf("
后序遍历序列
");    
117     postOrderTr(root);    
118     printf("
");
119 
120     return 0;
121 }

View Code

编译与执行:

1 g++ -o construct construct.cpp
2 ./construct

本文完。