?如題：

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和 中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序 遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

?根據(jù)前序和中序數(shù)列重建二叉樹，這道題，還有一道類似題，根據(jù)后續(xù)和中序數(shù)列重建二叉樹。兩題解法完全一樣，僅僅方向不同。這是學(xué)習(xí)二叉樹的時候必做的題型，和遍歷二叉樹性質(zhì)類似。

看題，我們知道，前序遍歷得到的數(shù)列，依次是各子樹的根節(jié)點，如根節(jié)點，根節(jié)點左子樹，根節(jié)點右子樹......，此外，中序遍歷數(shù)列中，根節(jié)點的值位于中間，左右兩邊依次是左右子樹。結(jié)合前序數(shù)列性質(zhì)，我們可以這樣做，先再前序數(shù)列求得根節(jié)點的值，然后，查找中序遍歷，此時，中序數(shù)列中，位于根節(jié)點左邊的數(shù)列即是左子樹，右邊的為右子樹。先后求得根節(jié)點的左子樹以及右子樹。之后，采用遞歸，依次求得節(jié)點的左右子樹即可。

后序遍歷也是一樣處理，只不過方向變反。后序遍歷數(shù)列，從后往前依次是根節(jié)點，根節(jié)點右子樹，根節(jié)點左子樹，即左右子樹求取順序和上述題型相反。

下面是本題的c++解法：

//模板題，先計算根節(jié)點，然后分別計算左子樹和右子樹的根節(jié)點 class Solution { public:TreeNode *constructTree(vector<int> pre,int *preStart, int preEnd, vector<int> vin, int vinStart, int vinEnd){int i;TreeNode *root;//特殊情況處理if (vinStart > vinEnd) return NULL;root = new TreeNode(pre[*preStart]);//找到左子樹和右子樹的范圍for (i = vinStart; i <= vinEnd; i++){if (pre[*preStart] == vin[i])break;}//指向下一個根節(jié)點*preStart = *preStart + 1;root->left = constructTree(pre, preStart, preEnd, vin,vinStart,i-1);root->right = constructTree(pre, preStart, preEnd, vin,i+1, vinEnd);return root;}TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {int preStart = 0;if (pre.empty()) return NULL;return constructTree(pre, &preStart, pre.size()-1,vin,0,vin.size()-1);} };

=============================================================================================

Linux應(yīng)用程序、內(nèi)核、驅(qū)動、后臺開發(fā)交流討論群(745510310)，感興趣的同學(xué)可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。

總結(jié)

以上是生活随笔為你收集整理的《剑指offer》c++版本 7.重建二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。