剑指offer——面试题7：重建二叉树-白红宇

剑指offer——面试题7：重建二叉树

阅读量：6866 次

发布时间：2019-06-26

本文共 7520 字，大约阅读时间需要 25 分钟。

1 // 面试题7：重建二叉树  2 // 题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输  3 // 入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,  4 // 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建出  5 // 图2.6所示的二叉树并输出它的头结点。  6   7 #include 
      
         8 #include 
       
          9 #include 
        
          10 #include
         
           11 using namespace std; 12  13 struct BinaryTreeNode 14 { 15     int                    m_nValue; 16     BinaryTreeNode*        m_pLeft; 17     BinaryTreeNode*        m_pRight; 18 }; 19  20 BinaryTreeNode* CreateBinaryTreeNode(int value) 21 { 22     BinaryTreeNode* pNode = new BinaryTreeNode(); 23     pNode->m_nValue = value; 24     pNode->m_pLeft = nullptr; 25     pNode->m_pRight = nullptr; 26  27     return pNode; 28 } 29  30 void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight) 31 { 32     if(pParent != nullptr) 33     { 34         pParent->m_pLeft = pLeft; 35         pParent->m_pRight = pRight; 36     } 37 } 38  39 void PrintTreeNode(const BinaryTreeNode* pNode) 40 { 41     if(pNode != nullptr) 42     { 43         printf("value of this node is: %d\n", pNode->m_nValue); 44  45         if(pNode->m_pLeft != nullptr) 46             printf("value of its left child is: %d.\n", pNode->m_pLeft->m_nValue); 47         else 48             printf("left child is nullptr.\n"); 49  50         if(pNode->m_pRight != nullptr) 51             printf("value of its right child is: %d.\n", pNode->m_pRight->m_nValue); 52         else 53             printf("right child is nullptr.\n"); 54     } 55     else 56     { 57         printf("this node is nullptr.\n"); 58     } 59  60     printf("\n"); 61 } 62  63 void PrintTree(const BinaryTreeNode* pRoot) 64 { 65     PrintTreeNode(pRoot); 66  67     if(pRoot != nullptr) 68     { 69         if(pRoot->m_pLeft != nullptr) 70             PrintTree(pRoot->m_pLeft); 71  72         if(pRoot->m_pRight != nullptr) 73             PrintTree(pRoot->m_pRight); 74     } 75 } 76  77 void DestroyTree(BinaryTreeNode* pRoot) 78 { 79     if(pRoot != nullptr) 80     { 81         BinaryTreeNode* pLeft = pRoot->m_pLeft; 82         BinaryTreeNode* pRight = pRoot->m_pRight; 83  84         delete pRoot; 85         pRoot = nullptr; 86  87         DestroyTree(pLeft); 88         DestroyTree(pRight); 89     } 90 } 91  92 BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder); 93  94 BinaryTreeNode* Construct(int* preorder, int* inorder, int length) 95 { 96     if(preorder == nullptr || inorder == nullptr || length <= 0) 97         return nullptr; 98  99     return ConstructCore(preorder, preorder + length - 1,100         inorder, inorder + length - 1);101 }102 103 BinaryTreeNode* ConstructCore104 (105     int* startPreorder, int* endPreorder,106     int* startInorder, int* endInorder107 )108 {109     // 前序遍历序列的第一个数字是根结点的值110     int rootValue = startPreorder[0];111     BinaryTreeNode* root = new BinaryTreeNode();112     root->m_nValue = rootValue;113     root->m_pLeft = root->m_pRight = nullptr;114 115     if(startPreorder == endPreorder)116     {117         if(startInorder == endInorder && *startPreorder == *startInorder)118             return root;119         else120         {121             std::logic_error ex("Invalid input.");122             throw std::exception(ex);123         }124        //     throw exception("Invalid input.");125     }126 127     // 在中序遍历中找到根结点的值128     int* rootInorder = startInorder;129     while(rootInorder <= endInorder && *rootInorder != rootValue)130         ++ rootInorder;131 132     if(rootInorder == endInorder && *rootInorder != rootValue)133     {134          std::logic_error ex("Invalid input.");135          throw std::exception(ex);136     }137      //   throw std::exception("Invalid input.");138 139     int leftLength = rootInorder - startInorder;140     int* leftPreorderEnd = startPreorder + leftLength;141     if(leftLength > 0)142     {143         // 构建左子树144         root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd,145             startInorder, rootInorder - 1);146     }147     if(leftLength < endPreorder - startPreorder)148     {149         // 构建右子树150         root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder,151             rootInorder + 1, endInorder);152     }153 154     return root;155 }156 157 // ====================测试代码====================158 void Test(char* testName, int* preorder, int* inorder, int length)159 {160     if(testName != nullptr)161         printf("%s begins:\n", testName);162 163     printf("The preorder sequence is: ");164     for(int i = 0; i < length; ++ i)165         printf("%d ", preorder[i]);166     printf("\n");167 168     printf("The inorder sequence is: ");169     for(int i = 0; i < length; ++ i)170         printf("%d ", inorder[i]);171     printf("\n");172 173     try174     {175         BinaryTreeNode* root = Construct(preorder, inorder, length);176         PrintTree(root);177 178         DestroyTree(root);179     }180     catch(std::exception& exception)181     {182         printf("Invalid Input.\n");183     }184 }185 186 // 普通二叉树187 //              1188 //           /     \189 //          2       3190 //         /       / \191 //        4       5   6192 //         \         /193 //          7       8194 void Test1()195 {196     const int length = 8;197     int preorder[length] = {
    1, 2, 4, 7, 3, 5, 6, 8};198     int inorder[length] = {
    4, 7, 2, 1, 5, 3, 8, 6};199 200     Test("Test1", preorder, inorder, length);201 }202 203 // 所有结点都没有右子结点204 //            1205 //           /206 //          2207 //         /208 //        3209 //       /210 //      4211 //     /212 //    5213 void Test2()214 {215     const int length = 5;216     int preorder[length] = {
    1, 2, 3, 4, 5};217     int inorder[length] = {
    5, 4, 3, 2, 1};218 219     Test("Test2", preorder, inorder, length);220 }221 222 // 所有结点都没有左子结点223 //            1224 //             \225 //              2226 //               \227 //                3228 //                 \229 //                  4230 //                   \231 //                    5232 void Test3()233 {234     const int length = 5;235     int preorder[length] = {
    1, 2, 3, 4, 5};236     int inorder[length] = {
    1, 2, 3, 4, 5};237 238     Test("Test3", preorder, inorder, length);239 }240 241 // 树中只有一个结点242 void Test4()243 {244     const int length = 1;245     int preorder[length] = {
    1};246     int inorder[length] = {
    1};247 248     Test("Test4", preorder, inorder, length);249 }250 251 // 完全二叉树252 //              1253 //           /     \254 //          2       3255 //         / \     / \256 //        4   5   6   7257 void Test5()258 {259     const int length = 7;260     int preorder[length] = {
    1, 2, 4, 5, 3, 6, 7};261     int inorder[length] = {
    4, 2, 5, 1, 6, 3, 7};262 263     Test("Test5", preorder, inorder, length);264 }265 266 // 输入空指针267 void Test6()268 {269     Test("Test6", nullptr, nullptr, 0);270 }271 272 // 输入的两个序列不匹配273 void Test7()274 {275     const int length = 7;276     int preorder[length] = {
    1, 2, 4, 5, 3, 6, 7};277     int inorder[length] = {
    4, 2, 8, 1, 6, 3, 7};278 279     Test("Test7: for unmatched input", preorder, inorder, length);280 }281 282 int main(int argc, char* argv[])283 {284     Test1();285     Test2();286     Test3();287     Test4();288     Test5();289     Test6();290     Test7();291 292     return 0;293 }