題目描述：給出二叉樹的后序和中序序列，輸出二叉樹的層序遍歷序列。

題目分析：中序遍歷為左根右，后序遍歷為左右根，所以后序遍歷的最后一個節點為根節點，在中序遍歷上找出根節點的位置，將樹分為左右兩個子樹。

使用 in[]，post[] 存儲中序后后序序列。假設某個分支二叉樹中序區間為[inL, inR]，后序區間為[postL，postR]，那么post[postR]就為該樹的根節點，根據根節點去中序中查找，找到根節點在中序中的位置為k。二叉樹左子樹的個數為numLeft=k-inL。左子樹的中序區間為[inL,k-1]，右子樹的中序區間[k+1,inR]；左子樹的后序區間為[postL,postL+numLeft-1]，右子樹的后序區間為[postL+numLeft,postR-1]。

創建樹時返回根節點的地址。最后層序遍歷樹，使用隊列，從根節點開始，將節點入隊，然后讀隊首，再出隊直至隊列為空。

代碼如下：

#include <iostream> #include <queue> using namespace std; const int N = 1010; int in_order[N], post_order[N]; int n;struct node {int data;node *lchild;node *rchild; };node *build(int inL, int inR, int postL, int postR) {if (inL > inR)return NULL;node *root;root = new node;root->data = post_order[postR];int k = inL;while (in_order[k] != root->data)k++;int numLeft = k - inL;root->lchild = build(inL, k - 1, postL, postL + numLeft - 1);root->rchild = build(k + 1, inR, postL + numLeft, postR - 1);return root; }void bfs(node *root) {int num = 0;queue<node *>q;q.push(root);while (q.size()) {node *now = q.front();q.pop();cout << now->data;num++;if (num < n)cout << " ";if (now->lchild != NULL)q.push(now->lchild);if (now->rchild != NULL)q.push(now->rchild);} }int main() {cin >> n;for (int i = 0; i < n; i++)cin >> in_order[i];for (int i = 0; i < n; i++)cin >> post_order[i];node *root = build(0, n - 1, 0, n - 1);bfs(root);return 0; }

測試結果：

題目分析鏈接：
https://blog.csdn.net/weixin_39851956/article/details/105253197

總結

以上是生活随笔為你收集整理的根据后序和中序求二叉树的层序的全部內容，希望文章能夠幫你解決所遇到的問題。

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