@算法學習
問題是：基于層序遍歷序列+中序遍歷序列唯一建立一棵樹，然后輸出前序，后序遍歷序列。
四種遍歷樹的思路以及代碼自然不必多言，有趣的是如何由層序+中序建立樹。
首先需要說的是，這個也是遞歸解法。
http://paste.Ubuntu.com/24084585/
既然是遞歸解法，就需要想當前層的問題，給定一個層序遍歷序列+中序遍歷序列，當前能確定的根結點就是層序序列的第一個值，拿這個去在中序中找到根結點的下標k，就劃分出來了左右子樹。 現在問題就有意思了，左子樹在層序中的序列不是在一團的，而是散開的，換句話說，左子樹的和右子樹的層序遍歷序列是交叉在一起的，怎么辦？
我們想，如果能夠有左子樹的層序遍歷序列和右子樹的層序遍歷序列就好了。
這個其實是非常漂亮的觀點，基于這個就能夠解決問題。
開兩個數組專門存左右子樹的遍歷序列即可。
我重寫的一個版本：
#include <stdio.h>#include <vector>#include <queue>using namespace std;const int maxn = 40;int in[maxn];vector<int> layer;vector<int> PRe,post; // 先存再輸出也行，但是耗費一點時間struct node{ int data; node* left; node* right;};node* newNode(int val){ node* Node = new node; Node->left = NULL; Node->right = NULL; Node->data = val; return Node;}void preOrder(node* root){ if(!root) return; pre.push_back(root->data); preOrder(root->left); preOrder(root->right);}void postOrder(node* root){ if(!root) return; postOrder(root->left); postOrder(root->right); post.push_back(root->data);}node* createFromLevelInOrder(vector<int> layer, int inL, int inR){ if(layer.size() == 0) // 如果層序用完了，表示遞歸邊界，可以往回歸 { return NULL; } // 處理當前層的問題 node* root = newNode(layer[0]); int k; //在中序中劃分 for(k = inL; k <= inR; k++) { if(layer[0] == in[k]) { break; //找到就跳出循環 } } vector<int> leftLayer; // 左子樹層序遍歷序列 vector<int> rightLayer; // 右子樹層序遍歷序列 for(int i = 1; i < layer.size(); i++) // 遍歷當前層序，劃分左右存儲起來 { bool isLeft = false; for(int j = inL; j < k; j++) { if(layer[i] == in[j]) { isLeft = true; break; //確定一個就跳出來，當前是在外層的大循環下 } } if(isLeft) { leftLayer.push_back(layer[i]); } else { rightLayer.push_back(layer[i]); } } // 尤其需要注意這里需要用root的左右指針去接下一層的構造 root->left = createFromLevelInOrder(leftLayer,inL, k - 1); root->right = createFromLevelInOrder(rightLayer,k + 1, inR); return root;}int main(){ int n; scanf("%d", &n); int temp; // 控制輸入 for(int i = 0; i < n; i++) { scanf("%d", &temp); layer.push_back(temp); //輸入層序遍歷序列 } for(int i = 0; i < n; i++) { scanf("%d", &in[i]); // 輸入中序遍歷序列 } node* root = createFromLevelInOrder(layer,0,n - 1); preOrder(root); postOrder(root); // 控制輸出 for(int i = 0; i < pre.size(); i++) { printf("%d", pre[i]); if(i < pre.size() - 1) { printf(" "); } } printf("/n"); for(int i = 0; i < post.size(); i++) { printf("%d", post[i]); if(i < post.size() - 1) { printf(" "); } } printf("/n"); return 0;}新聞熱點
疑難解答
