POJ

POJ2255 OpenJ_Bailian2255 ZOJ1944 HRBUST2022 Tree Recovery

題目連結 POJ
題目連結 OpenJ_Bailian
題目連結 ZOJ
題目連結 HRBUST

  • 題意：給定一顆二元樹的前序和中序，求其後序。
  • 題解：前序第一個為根，藉此可以找出中序的根和左右子樹的範圍。依序訪問左子樹、右子樹，並輸出根，就可以得到後序。
    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
    #pragma GCC optimize(2)
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <iostream>
    #include <map>
    #include <string>
    #include <vector>
    using namespace std;
    typedef long long LL;
    const int INF = 1e9;
    const int MXN = 1e5 + 5;
    const int MXV = 3e5 + 5;
    const LL MOD = 10009;
    const LL seed = 31;
    #define MP make_pair
    #define PB push_back
    #define F first
    #define S second
    #define FOR(i, L, R) for (int i = L; i != (int)R; ++i)
    #define FORD(i, L, R) for (int i = L; i != (int)R; --i)
    #define IOS                                                                    \
        cin.tie(NULL);                                                             \
        cout.tie(NULL);                                                            \
        ios_base::sync_with_stdio(false);

    string preorder, inorder;
    void dfs(int L1, int R1, int L2, int R2)
    {
        // cout << L1 << ' ' << R1 << ' ' << L2 << ' ' << R2 << '\n';
        int root1 = L1, root2 = 0;
        if (L1 + 1 > R1 || L2 + 1 > R2)
        {
            return;
        }
        if (L1 + 1 == R1 && L2 + 1 == R2)
        {
            cout << preorder[L1];
            return;
        }
        FOR(i, L2, R2) if (preorder[root1] == inorder[i])
        {
            root2 = i;
            break;
        }
        dfs(L1 + 1, L1 + 1 + (root2 - L2), L2, root2);
        dfs(L1 + 1 + (root2 - L2), R1, root2 + 1, R2);
        cout << preorder[root1];
    }

    int main()
    {
        IOS;
        while (cin >> preorder >> inorder)
        {
            dfs(0, (int)inorder.size(), 0, (int)inorder.size());
            cout << '\n';
        }
    }

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts