Zhao70's Blog

PAT1020 Tree Traversals

发表于 | 分类于

题目大意

PAT1020

给定一棵树的后序和前序遍历, 求树的层序遍历.

思路

不断进行递归, 当长度为 0 时, 返回空指针.
柳婼的博客是利用一个大的数组进行存储结点, 但题目中给出了30 个结点, 最坏情况下需要 2 ^ 31 - 1 个结点. 虽然这道题用数组存储结点并不会出错, 但是为了 robust. 还是动态的创建结点比较好~

坑

要充分理解函数传参当中 postLoc, inLoc 是绝对位置, 而 length 为相对长度.
函数参数写错了就很坑 QAQQQQQQQQQ

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct Node{
    Node *leftChild, *rightChild;
    int data;
    Node(int d, Node* l, Node* r)
        : data(d), leftChild(l), rightChild(r){};
};
vector<int> postOrder;
vector<int> inOrder;
Node* constructTree(int postLoc, int inLoc, int length){
    // cout << length << endl;
    if(length <= 0)
        return NULL;
    Node* temp = new Node(postOrder[postLoc + length - 1], NULL, NULL);
    int loc = inLoc;
    for(; loc < inLoc + length
            && inOrder[loc] != postOrder[postLoc + length - 1]; loc++);
    temp->leftChild = constructTree(postLoc, inLoc, loc - inLoc);
    //右子树的长度 为 中序的起始位置 + 中序长度 得到 中序终止位置
    //               再减去 左子树 和 根节点的长度和.
    temp->rightChild = constructTree(postLoc + loc - inLoc, loc + 1, inLoc + length - loc - 1);
    return temp;
}
int nNode;
void prTree(Node* root){
    queue<Node*> que;
    que.push(root);
    int cnt = 0;
    while(!que.empty()){
        cout << que.front()-> data;
        cnt++;
        if(cnt != nNode)
            cout << " ";
        if(que.front()->leftChild != NULL)
            que.push(que.front()->leftChild);
        if(que.front()->rightChild != NULL)
            que.push(que.front()->rightChild);
        que.pop();
    }
}
int main(){
    cin >> nNode;
    for(int i = 0; i < nNode; ++i){
        int data;
        cin >> data;
        postOrder.push_back(data);
    }
    for(int i = 0; i < nNode; ++i){
        int data;
        cin >> data;
        inOrder.push_back(data);
    }
    Node* root = constructTree(0, 0, nNode);
    prTree(root);
    return 0;
}