題目

1020 Tree Traversals （25 分）
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

Sample Output:
4 1 6 3 5 7 2

分析題目

日常查單詞環(huán)節(jié)：postorder and inorder traversal sequences 后序和中序遍歷序列
level order traversal sequence 層序遍歷序列
根據(jù)題意，這是一個(gè)已知后序和先序遍歷序列求層序遍歷序列的題目

先去學(xué)習(xí)了一下柳神的關(guān)于已知后序與中序輸出前序

后序中序輸出前序

代碼

首先說(shuō)明幾個(gè)變量
root 根結(jié)點(diǎn)的位置（后序） i 根節(jié)點(diǎn)的位置（中序）
b 樹(shù)開(kāi)始遍歷的位置（中序） e 樹(shù)結(jié)束遍歷的位置（中序）

后序?yàn)樽笥腋?，中序?yàn)樽蟾?br> 后序序列中最后一個(gè)肯定是樹(shù)的根結(jié)點(diǎn)，從最后一個(gè)開(kāi)始，將中序分成兩撥。
左子樹(shù)遍歷的起始點(diǎn)為b, 結(jié)束點(diǎn)為i-1，根節(jié)點(diǎn)為root-1-(e-i)
右子樹(shù)遍歷的起始點(diǎn)為i+1,結(jié)束點(diǎn)為e，根節(jié)點(diǎn)為root-1

#include <iostream>
using namespace std;
int post[] = {3, 4, 2, 6, 5, 1};//后序序列
int in[] = {3, 2, 4, 1, 6, 5};//中序序列

void pre(int b, int e, int root)
{
    if(b > e)
        return;
    int i = b;
    while(i< e && post[root] != in[i]) i++;
    cout << post[root] << " " << i << " " << e << endl;
    pre(b, i-1, root-1-(e-i));
    cout << "i: " << i << " b: " << b << " e: " << e << " root:" << root << endl;
    pre(i+1, e, root-1);
}

int main()
{
    pre(0, 5, 5);
    return 0;
}

好了學(xué)習(xí)完成，我們來(lái)看這道題，這題是一個(gè)已知后序和中序遍歷序列求層序遍歷序列的題目，思路是一樣的。

后序?yàn)樽笥腋?，中序?yàn)樽蟾?br> 后序序列中最后一個(gè)肯定是樹(shù)的根結(jié)點(diǎn)，從最后一個(gè)開(kāi)始，將中序分成兩撥。
左子樹(shù)遍歷的起始點(diǎn)為b, 結(jié)束點(diǎn)為i-1，根節(jié)點(diǎn)為root-1-(e-i)
右子樹(shù)遍歷的起始點(diǎn)為i+1,結(jié)束點(diǎn)為e，根節(jié)點(diǎn)為root-1

為了輸出層序，則另設(shè)一個(gè)變量index跟蹤其層數(shù)

代碼

#include <iostream>
#include <vector>
using namespace std;
vector<int> post, in, level(100000, -1);
void pre(int root, int b, int e, int index)
{
    int i = b;
    if(b > e)
        return;
    while(i < e && post[root]!= in[i]) i++;
    level[index] = post[root];
    pre(root-1-(e-i), b, i-1, index*2+1);
    pre(root-1, i+1, e, index*2+2);
}


int main()
{
    int N;
    int cnt = 0;
    cin >> N;
    post.resize(N);
    in.resize(N);
    for(int i = 0; i<N; i++) cin >> post[i];
    for(int i = 0; i<N; i++) cin >> in[i];
    pre(N-1, 0, N-1, 0);
    for(int i = 0; i<level.size(); i++)
    {
        if(level[i] != -1)
        {
            if(cnt!= 0)
                cout << " ";
            cout << level[i];
            cnt++;
        }
        if(cnt == N)
            break;
    }
    return 0;
}

總結(jié)：

柳神太強(qiáng)了，但有個(gè)點(diǎn)沒(méi)弄懂，就是如果用index去記錄結(jié)點(diǎn)在樹(shù)中的位置，題目給的邊界條件為N<=30，按理說(shuō)，最大應(yīng)是2^30，這個(gè)數(shù)遠(yuǎn)大于代碼里的100000，但還是能夠AC了，這個(gè)地方?jīng)]太懂。
這題典型的已知樹(shù)的其中兩個(gè)序列，求第三個(gè)序列
通過(guò)柳神代碼里還學(xué)會(huì)了vector中resize的用法，和初始化一個(gè)固定長(zhǎng)并填入初始值的方法，這樣使得代碼看起來(lái)更加簡(jiǎn)潔高效。
每日吹柳神