PAT甲级1138Postorder Traversal

Posted on | | Visitors:
Words count in article: 564 字 | Reading time ≈ 2 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805345078067200

题解

题目要求

假设二叉树中所有结点的值都是互异的正整数，给定二叉树的先序和后序遍历，请输出该树后序遍历的第一个数字。

  • 输入
    • N：正整数，不超过50000，二叉树中结点的数量
    • 先序遍历结果
    • 中序遍历结果

解题思路

  • 根据先序遍历和中序遍历结果可以确定一颗树，这道题的关键就是如何确定出这颗树并遍历它。

    可以参考PAT甲级1151LCA in a Binary Tree，这道题里也是根据先序遍历和中序遍历结果确定出了一棵树。

  • 设置全局flag判断是否是该树后序遍历的第一个数字，如果是则输出，不是则不输出

代码

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
// Problem: PAT Advanced 1138
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805345078067200
// Tags: Tree DFS

#include <iostream>
#include <vector>
#include <map>
using namespace std;

vector<int> preOrder; // 先序遍历结果
vector<int> inOrder; // 中序遍历结果
map<int, int> inPos; // 结点到中序遍历结果inOrder索引的映射
bool firstIsPrinted = false; // 为true代表后序遍历时的第一个结点已经输出

void postOrderTraverse(int inLeft, int inRight, int preRoot){
    if (firstIsPrinted) // 只输出后序遍历的第一个结点即可
        return ;
    if (inRight < inLeft) // 该树不存在
        return ;

    int inRoot = inPos[preOrder[preRoot]]; // 当前树的根结点在中序遍历结果inOrder中的索引
    
    // 后序遍历
    postOrderTraverse(inLeft, inRoot - 1, preRoot + 1);        // 遍历左子树并判断左子树是否存在
    postOrderTraverse(inRoot + 1, inRight, preRoot + 1 + (inRoot - inLeft)); // 遍历右子树并判断右子树是否存在
    if (!firstIsPrinted){ // 只输出后序遍历的第一个结点即可
        printf("%d", inOrder[inRoot]);
        firstIsPrinted = true;
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    preOrder.resize(n + 1);
    inOrder.resize(n + 1);

    for (int i = 1; i <= n; i++) // 读取先序遍历结果
        scanf("%d", &preOrder[i]);
    for (int i = 1; i <= n; i++){  // 读取中序遍历结果
        scanf("%d", &inOrder[i]);
        inPos[inOrder[i]] = i;
    }

    postOrderTraverse(1, n, 1);

    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!