中序+前序與中序+後序之重建二叉樹
- 2019 年 11 月 23 日
- 筆記
重建二叉樹
1.題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重複的數字。例如輸入前序遍歷序列 {1, 2, 4, 7, 3, 5, 6, 8} 和中序遍歷序列 {4, 7, 2, 1, 5, 3, 8, 6}，則重建出如下圖所示的二叉樹並返回它的頭結點。
2.二叉樹四種遍歷方式
l例如一個二叉樹層次遍歷順序為[1,2,3,4,5,6,7],那麼：
前：[1, 2, 4, 5, 3, 6, 7]
中：[4, 2, 5, 1, 5, 3, 7]
後：[4, 5, 2, 6, 7, 3, 1]
層：[1, 2, 3, 4, 5, 6, 7]
- 前序遍歷：先訪問根結點，再訪問左子結點，最後訪問右子結點。
- 中序遍歷：先訪問左子結點，再訪問根結點，最後訪問右子結點。
- 後序遍歷：先訪問左子結點，再訪問右子結點，最後訪問根結點。
3.中序+前序
回到這個題目，我們知道中序+前序可以構建一顆二叉樹，而本題就是通過這個方式來構建，當然後序+中序也可以構建，但是前序+後序是不可以的。舉個例子：
D / E
前序遍歷：DE, 後序遍歷：ED
則下面樹的結構也滿足前序和後序遍歷的序列。
D E
即這種情況，不能唯一確定一棵樹。
當前這個題目(前序+中序)解決方案如下：
- 不使用原數組
- 使用原數組-採用左節點個數構建
- 使用原數組-採用右節點個數構建
（1）不使用原數組
思路很簡單，對比中序列與前序：
前序：[1, 2, 4, 5, 3, 6, 7] 中序：[4, 2, 5, 1, 5, 3, 7] i
首先構建根，其次遞歸構建自己的左右孩子，最後返回根就可以了。
每次在中序遍歷中找到根節點位置，然後劃分左右孩子。
TreeNode *reConstructBinaryTree(vector<int> pre, vector<int> vin) { if (pre.empty() || vin.empty()) return NULL; TreeNode *root = new TreeNode(pre[0]); vector<int> lpre, lvin, rpre, rvin; for (int i = 0; i < vin.size(); i++) { if (vin[i] == pre[0]) { lpre = vector<int>(pre.begin() + 1, pre.begin() + i + 1); lvin = vector<int>(vin.begin(), vin.begin() + i); rpre = vector<int>(pre.begin() + i + 1, pre.end()); rvin = vector<int>(vin.begin() + i + 1, vin.end()); root->left = reConstructBinaryTree(lpre, lvin); root->right = reConstructBinaryTree(rpre, rvin); } } return root; }
這種方法非常好理解，缺點是並不是在原來的數組上操作。
下面這種方法是直接在原來的數組上操作的，但是下標邊界直接看不是很明白，需要配合畫圖才能理解。
再看下面這個：
前序：[1, 2, 4, 5, 3, 6, 7] pStart pEnd 中序：[4, 2, 5, 1, 5, 3, 7] vStart i vEnd
中序遍歷得出如下結論：
- 左子結點長度 = i – vStart
- 右子結點長度 = vEnd – i
所以對於左子樹來說：
前序遍歷下標範圍 = [pStart+1,pStart+i-vStart]
中序遍歷下標範圍 = [vStart,i-1]
對於右子樹來說
前序遍歷下標範圍 = [pStart+i-vStart+1,pEnd]
中序遍歷下標範圍 = [i+1,vEnd]
於是第二種方法出來了。
（2）使用原數組-採用左節點個數構建
TreeNode *preForConstructBinaryTree(vector<int> pre, vector<int> vin) { return preAndVin(pre, 0, pre.size() - 1, vin, 0, vin.size() - 1); } // 前序+中序 TreeNode *preAndVin(const vector<int> &pre, int pStart, int pEnd, const vector<int> &vin,int vStart, int vEnd) { // 遞歸終止條件 if (pStart > pEnd || vStart > vEnd) return NULL; TreeNode *root = new TreeNode(pre[pStart]); // 重建根節點 // 重建左右子樹 for (int i = vStart; i <= vEnd; i++) { if (vin[i] == pre[pStart]) { root->left = preAndVin(pre, pStart + 1, pStart + i - vStart, vin, vStart, i - 1); root->right = preAndVin(pre, pStart + i - vStart + 1, pEnd, vin, i + 1, vEnd); } return root; }
（3）使用原數組-採用右節點個數構建
另外，我們還可以使用右子結點長度來構建。
所以對於左子樹來說：
前序遍歷下標範圍 = [pStart+1,pEnd-(vEnd-i)]
中序遍歷下標範圍 = [vStart,i-1]
對於右子樹來說
前序遍歷下標範圍 = [pEnd-(vEnd-i)+1,pEnd]
中序遍歷下標範圍 = [i+1,vEnd]
只需要將上述左右子樹構建改為：
root->left = preAndVin(pre, pStart + 1, pEnd - (vEnd - i), vin, vStart, i - 1); root->right = preAndVin(pre, pEnd - (vEnd - i) + 1, pEnd, vin, i + 1, vEnd);
4.中序+後序
既然這道題是前序+中序，那麼我們在琢磨一下中序+後序唄，同樣的道理，也是上面兩種。
（1）不使用原數組
TreeNode *reConstructBinaryTree1(vector<int> post, vector<int> vin) { if (post.empty() || vin.empty()) return NULL; TreeNode *root = new TreeNode(post[post.size() - 1]); vector<int> lpost, lvin, rpost, rvin; for (int i = 0; i < vin.size(); i++) { if (vin[i] == post[post.size() - 1]) { // 後序 左半邊 lpost = vector<int>(post.begin(), post.begin() + i); // 中序 左半邊 lvin = vector<int>(vin.begin(), vin.begin() + i); // 後序 右半邊 rpost = vector<int>(post.begin() + i, post.end() - 1); // 前序 右半邊 rvin = vector<int>(vin.begin() + i + 1, vin.end()); root->left = reConstructBinaryTree1(lpost, lvin); root->right = reConstructBinaryTree1(rpost, rvin); } } return root; }
（2）使用原數組-採用左節點個數構建
後：[4, 5, 2, 6, 7, 3, 1] pStart pEnd 中：[4, 2, 5, 1, 5, 3, 7] vStar i vEnd
- 左子結點長度 = i – vStart
- 右子結點長度 = vEnd – i
所以對於左子樹來說：
後序遍歷下標範圍 = [pStart,pStart+i-vStart-1]
中序遍歷下標範圍 = [vStart,i-1]
對於右子樹來說
後序遍歷下標範圍 = [pStart+i-vStart,pEnd-1]
中序遍歷下標範圍 = [i+1,vEnd]
// 中序+後序 TreeNode *postAndVin(const vector<int> &post, int pStart, int pEnd, const vector<int> &vin,int vStart, int vEnd) { // 遞歸終止條件 if (pStart > pEnd || vStart > vEnd) return NULL; int rootVal = post[pEnd]; TreeNode *root = new TreeNode(rootVal); // 重建根節點 // 重建左右子樹 for (int i = vStart; i <= vEnd; i++) { if (vin[i] == rootVal) { root->left = postAndVin(post, pStart, pStart + i - vStart - 1, vin, vStart, i - 1); root->right = postAndVin(post, pStart + i - vStart, pEnd - 1, vin, i + 1, vEnd); } } return root; } };
（3）使用原數組-採用右節點個數構建
所以對於左子樹來說：
前序遍歷下標範圍 = [pStart,pEnd – (vEnd – i) – 1]
中序遍歷下標範圍 = [vStart,i-1]
對於右子樹來說
後序遍歷下標範圍 = [pEnd-(vEnd-i),pEnd-1]
中序遍歷下標範圍 = [i+1,vEnd]
所以，上述程式碼改為：
// method 2 root->left = postAndVin(post, pStart, pEnd - (vEnd - i) - 1, vin, vStart, i - 1); root->right = postAndVin(post, pEnd - (vEnd - i), pEnd - 1, vin, i + 1, vEnd);
