記錄來自《劍指offer》上的算法題目。
題目如下：

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重構出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果都不含重復的數字。

二叉樹的結點定義如下：

struct BinaryTreeNode{int m_nValue;BinaryTreeNode* m_pLeft;BinaryTreeNode* m_pRight; };

實現代碼如下：

BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder){// 前序遍歷的第一個數字就是根結點的值int rootValue = startPreorder[0];BinaryTreeNode* root = new BinaryTreeNode();root->m_nValue = rootValue;root->m_pLeft = root->m_pRight = NULL;if (startPreorder == endPreorder){if (startInorder == endInorder && *startPreorder == *startInorder)return root;elsethrow std::exception("Invalid input.");}// 在中序遍歷中找到根結點的值int *rootInorder = startInorder;while (rootInorder <= endInorder && *rootInorder != rootValue)++rootInorder;if (rootInorder == endInorder && *rootInorder != rootValue)throw std::exception("Invalid input.");int leftLength = rootInorder - startInorder;int* leftPreorderEnd = startPreorder + leftLength;if (leftLength > 0){// 構建左子樹root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, startInorder, rootInorder - 1);}if (leftLength < endPreorder - startPreorder){// 構建右子樹root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder, rootInorder + 1, endInorder);}return root; } // 重建二叉樹，根據輸入的前序序列和中序序列 BinaryTreeNode* Construct(int* preorder, int* inorder, int length){if (preorder == NULL || inorder == NULL || length <= 0)return NULL;return ConstructCore(preorder, preorder + length - 1, inorder, inorder + length - 1); }

測試代碼如下：

// 前序遍歷輸出 void PreOutput(BinaryTreeNode* root){if (root == NULL)return;cout << root->m_nValue << " ";PreOutput(root->m_pLeft);PreOutput(root->m_pRight); } // 中序遍歷輸出 void InOutput(BinaryTreeNode* root){if (root == NULL)return;InOutput(root->m_pLeft);cout << root->m_nValue << " ";InOutput(root->m_pRight); }// 測試 int main(void){// 不完全二叉樹int pre1[] = {1,2,4,7,3,5,6,8};int in1[] = {4,7,2,1,5,3,8,6};BinaryTreeNode* root = Construct(pre1, in1, 8);cout << "不完全二叉樹前序遍歷輸出：";PreOutput(root);cout << endl;cout << "中序遍歷輸出：";InOutput(root);cout << endl;// 完全二叉樹int pre2[] = { 1, 2, 4, 8, 9, 5, 3, 6, 7 };int in2[] = { 8, 4, 9, 2, 5, 1, 6, 3, 7 };root = Construct(pre2, in2, 9);cout << "\n完全二叉樹前序遍歷輸出：";PreOutput(root);cout << endl;cout << "中序遍歷輸出：";InOutput(root);cout << endl;// 所有結點都沒有右子結點的二叉樹，即左斜樹int pre3[] = { 1, 2, 3, 4, 5 };int in3[] = { 5, 4, 3, 2, 1 };root = Construct(pre3, in3, 5);cout << "\n左斜樹前序遍歷輸出：";PreOutput(root);cout << endl;cout << "中序遍歷輸出：";InOutput(root);cout << endl;// 右斜樹int pre4[] = { 1, 2, 3, 4, 5 };int in4[] = { 1, 2, 3, 4, 5 };root = Construct(pre4, in4, 5);cout << "\n右斜樹前序遍歷輸出：";PreOutput(root);cout << endl;cout << "中序遍歷輸出：";InOutput(root);cout << endl;// 只有一個結點的二叉樹int pre5[] = { 5 };int in5[] = { 5 };root = Construct(pre5, in5, 1);cout << "\n一個結點的二叉樹前序遍歷輸出：";PreOutput(root);cout << endl;cout << "中序遍歷輸出：";InOutput(root);cout << endl;// 二叉樹的根結點指針是NULLint pre7[] = { 5 };int in7[] = { 5 };root = Construct(pre5, in5, 0);system("pause");return 0; }

在函數ConstructCore中，先根據前序序列的第一個數字創建根結點，然后在中序序列中找到根結點的位置，這樣就能確定左右子樹的數量，在前序遍歷和中序遍歷的序列中劃分了左、右子樹結點的值后，就可以遞歸地調用函數ConstructCore，去分別構建它的左右子樹。

完整的例子可以查看我的Github。

總結

以上是生活随笔為你收集整理的剑指offer--重建二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。