重建二叉樹
引言
問題：現(xiàn)有二叉樹的后序遍歷序列與中序遍歷序列饰迹，能否求原二叉樹？
答案是肯定的，并且前序與中序也可以得到原二叉樹赦颇。
本文就如何使用這兩種序列組合如何重建二叉樹進行討論。
首先赴涵，定義二叉樹的遍歷媒怯。
二叉樹的遍歷
對于一個二叉樹的遍歷，有以下原則：
- 遇到一個根節(jié)點髓窜，先訪問左節(jié)點扇苞，再訪問右節(jié)點
而前，后寄纵，中序遍歷分別指根節(jié)點在訪問左右節(jié)點之前鳖敷，之間，之后程拭。
如何重建哄陶？
那么根據(jù)二叉樹遍歷的定義，對一個最簡單的只有一個根節(jié)點與左右節(jié)點的二叉樹哺壶，來嘗試重建屋吨。
設一個二叉樹為下圖左所示，它的前山宾，中至扰，后序遍歷序列分別如下圖右所示：
二叉樹遍歷
假設我們只知道后序與中序，如何重建呢资锰？
- 顯然敢课，后序的最后一個數(shù)字就是根節(jié)點，也就是 3 是根節(jié)點。
- 在中序中找到3直秆，它的左邊是左節(jié)點濒募，右邊是右節(jié)點。
- 最終重建到二叉樹：根為3圾结，左節(jié)點為7瑰剃，右節(jié)點為1
由上方重建過程思考后，可以推廣：
對于更復雜的二叉樹筝野，將其先看作上圖模型的二叉樹晌姚，重建得到根節(jié)點與暫時混亂的左右節(jié)點，再遞歸的將左右節(jié)點依次重建為子二叉樹歇竟，即可完成整個二叉樹的重建挥唠。
在得到根節(jié)點之后，需要在中序遍歷序列中尋找根節(jié)點的位置焕议，并將中序序列拆分為左右部分宝磨。所以要求序列中不能有相同的數(shù)字，這是序列可重建二叉樹的前提盅安。
編碼抽象
將重建思路抽象之后懊烤，我們可以得到如下過程來重建二叉樹：
定義二叉樹節(jié)點
struct TreeNode {
int data;
TreeNode* left = NULL;
TreeNode* right = NULL;
};
設有后序序列vector<int> post與中序序列vector<int> in，現(xiàn)在我們將二叉樹重建到以TreeNode* node為根節(jié)點的二叉樹中宽堆。
1. 取出post的最后一個數(shù)R腌紧，則R為二叉樹的根節(jié)點
2. 在in中尋找R的位置
3. 從R拆分為左右子二叉樹的中序序列：inleft、inright
4. 在post中畜隶，從左到右取出inleft.size()個數(shù)字壁肋，其組成的序列為左子二叉樹的后序序列postleft
5. 類比4得到右子二叉樹的后序序列postright
6. 分別根據(jù)inleft與postleft重建左子二叉樹到node->left
7. 類比6重建右子二叉樹到node->right
實現(xiàn)
void getTree(vector<int> post, vector<int> in, TreeNode* node) {
vector<int> inleft, inright;
vector<int> postleft, postright;
if (post.size() == 0) return;
int rootNum = post[post.size() - 1];
post.pop_back();
node->data = rootNum;
// 將中序遍歷拆開
bool flag = false;
for (int i = 0; i < in.size(); i++) {
if (in[i] == rootNum) {
flag = true;
continue;
}
if (!flag)
inleft.push_back(in[i]);
else
inright.push_back(in[i]);
}
// 將后序遍歷拆開
for (int i = 0; i < post.size(); i++) {
if (i < inleft.size()) {
postleft.push_back(post[i]);
} else {
postright.push_back(post[i]);
}
}
if (inleft.size() > 0) {
node->left = new TreeNode;
getTree(postleft, inleft, node->left);
}
if (inright.size() > 0) {
node->right = new TreeNode;
getTree(postright, inright, node->right);
}
}
全文完。
我是誰籽慢？
我是iimT浸遗，大學生，技術(shù)宅箱亿，計算機科技愛好者跛锌，電音小王子。
我的博客：www.iimt.me
我在Weibo：@_iimT
我在B站：https://space.bilibili.com/69824765/#/
想看到我的更多更新的話届惋，很樂意你關(guān)注我髓帽！
你是誰？
歡迎在文后留下評論脑豹，一起討論郑藏，歡迎認識新朋友。
如果你也有博客瘩欺，在分享你的東西必盖，歡迎交流拌牲、友鏈(本人博客底部可申請)。
下一篇見~
