CYK的博客

welcome

0%

二叉树重建 binary tree rebuild

Posted on Edited on

L2-006 树的遍历 (25 分)

题目描述

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

1
2
3
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

1
4 1 6 3 5 7 2

思路分析

首先看后续遍历

对于后序遍历根节点一定是最后访问，于是开可以确定根节点一定是4

2 3 1 5 7 6 4

再看中序遍历

1 2 3 4 5 6 7

现在已知根节点为4，

所以左子树的中序遍历为

1 2 3

右子树的中序遍历为

5 6 7

再回到后序遍历中，已知左子树和右子树的划分，

所以 左子树后续遍历为

2 3 1

右子树后续遍历为

5 7 6

分割后如下图所示

图1
图1

继续分割，根据后续遍历

左侧123中1为根节点

右侧567中6为根节点

图2
图2
图3
图3

代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <vector>
#include <stdio.h>
#include <queue>

using namespace std;

struct TreeNode
{
    TreeNode* left;
    TreeNode* right;
    int No;
};

bool myfind(vector<int> a, int num){
    for (int i : a)
    {
        if ( i == num) return true;
    }
    return false;
}

void build(vector<int> b_ord, vector<int> m_ord, TreeNode* root){
    int size = b_ord.size();
    root->No = b_ord[size-1];
    if (size == 1)
    {
        // base case 最简单的情况，只有一个节点
        root->left = nullptr;
        root->right = nullptr;
        return;
    }    
    TreeNode* l = new TreeNode();
    TreeNode* r = new TreeNode();
    vector<int> l_mid;
    vector<int> r_mid;
    vector<int> l_behind;
    vector<int> r_behind;
    bool f = false;
    // 划分中序遍历 为 左子树 右子树两部分
    for (int i = 0; i < size; i++)
    {
        if (b_ord[size-1] == m_ord[i]) f = true;
        else
        {
            if (!f) l_mid.push_back(m_ord[i]);
            else r_mid.push_back(m_ord[i]);        
        }
    }
    // 划分后续遍历 为 左子树 右子树两部分
    for (int i = 0; i < size; i++)
    {
        if (myfind(l_mid, b_ord[i])) 
        {
            l_behind.push_back(b_ord[i]);
        }
        if (myfind(r_mid, b_ord[i])) 
        {
            r_behind.push_back(b_ord[i]);
        }
    }    
    if (l_mid.size() > 0) build(l_behind, l_mid, l); // 递归构建
    else l = nullptr;
    if (r_mid.size() > 0) build(r_behind, r_mid, r);
    else r = nullptr;
    root->left = l;
    root->right = r;
    return;
}

void visit(TreeNode* root, int n){
    // 层序遍历 其实就是BFS 用一个队列就可以解决
    queue<TreeNode*> q;
    q.push(root);
    int cnt = 0;
    while (!q.empty())
    {
        TreeNode* p = q.front();
        q.pop();
        if (cnt != n-1) cout << p->No << ' ';
        else cout << p->No;
        cnt++;
        if (p->left) q.push(p->left);
        if (p->right) q.push(p->right);
    }
    
}

int main()  
{
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout); // 输入输出重定向，方便调试
    
    int n;
    cin >> n;

    vector<int> behind_ord(n, 0);
    vector<int> mid_ord(n, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> behind_ord[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> mid_ord[i];
    }

    TreeNode* root = new TreeNode();
    build(behind_ord, mid_ord, root);

    visit(root, n);
    return 0;
}

很久没更新了，最近比较忙。今天刷完题才想起来可以顺手更新一下。